Wall#7761
Jan-Ji is building a wall from bricks of the same size. The wall consists of columns, numbered from left to right from to n - 1. The height of a column is the number of bricks in it. Columns may have different heights.
The construction proceeds as follows. Initially, all columns contain no bricks. Then Jan-Ji performs actions, each of which is either adding or removing bricks. The construction is considered finished after all actions are performed.
Before each action, Jan-Ji chooses some interval of consecutive columns and a height value . After that, he performs one of the following actions:
addition: in all columns of the chosen interval whose height is less than , the number of bricks becomes equal to . Columns with height at least remain unchanged;
removal: in all columns of the chosen interval whose height is greater than , the number of bricks becomes equal to . Columns with height at most remain unchanged.
Determine the final shape of the wall.
The first line contains two integers and k~(1 \le n \le 2 \cdot 10^6, 1 \le k \le 5 \cdot 10^5) — the number of columns in the wall and the number of operations.
Each of the following lines contains four values:
op_i — the type of operation: corresponds to addition, to removal.
The indices of the columns in the -th operation range from left_i to right_i inclusive. It is guaranteed that left_i \le right_i.
height_i — the height parameter in this operation.
Print integers, one per line. Line should contain the final number of bricks in column i~(0 \le i \le n - 1).
Suppose there are columns and wall modification operations. In all queries, the interval boundaries are inclusive. The state of the wall after each operation is shown below.
Since initially the heights of all columns are zero, after phase each column from to will contain bricks. Columns and remain empty.
In phase , bricks are removed in columns from to until each of them contains brick. Column remains empty. Columns from to are outside the query interval, so they do not change.
In phase , no changes occur in columns from to , since their height does not exceed .
After action , the number of bricks in columns , , and increases to .
After action , column contains bricks.
Action removes all bricks in columns and .
Example 1