There is an array of $n$ elements, initially filled with zeros. You need to write a data structure that processes two types of queries:

• assign value $v$ to all elements on the segment from $l$ to $r−1$,
• find the segment with maximal sum.

The first line contains two numbers $n,m\ (1≤n,m≤100,000)$, the size of the array and the number of operations. 

The following lines contain the description of the operations. 

The description of each operation is as follows: l r v: assign the value $v$ to all elements on the interval from $l$ to $r−1\ (0≤l<r≤n,\ −10^9≤v≤10^9)$.

Print $m$ lines: the maximum sum of numbers on a segment after each operation. Please note that this segment may be empty (so the sum on it will be equal to 0).