Wall
Jian-Jia is building a wall by stacking bricks of the same size together. This wall consists of n columns of bricks, which are numbered 0 to n − 1 from left to right. The columns may have different heights. The height of a column is the number of bricks in it.
Jian-Jia builds the wall as follows. Initially there are no bricks in any column. Then, Jian-Jia goes through k phases of adding or removing bricks. The building process completes when all k phases are finished. In each phase Jian-Jia is given a range of consecutive brick columns and a height h, and he does the following procedure:
In an adding phase, Jian-Jia adds bricks to those columns in the given range that have less than h bricks, so that they have exactly h bricks. He does nothing on the columns having h or more bricks.
In a removing phase, Jian-Jia removes bricks from those columns in the given range that have more than h bricks, so that they have exactly h bricks. He does nothing on the columns having h bricks or less.
Your task is to determine the final shape of the wall.
Example
We assume that there are 10 brick columns and 6 wall building phases. All ranges in the following table are inclusive. Diagrams of the wall after each phase are shown below.
Since all columns are initially empty, after phase 0 each of the columns 1 to 8 will have 4 bricks. Columns 0 and 9 remain empty.
In phase 1, the bricks are removed from columns 4 to 8 until each of them has 1 brick, and column 9 remains empty. Columns 0 to 3, which are out of the given range, remain unchanged.
Phase 2 makes no change since columns 3 to 6 do not have more than 5 bricks.
After phase 3 the numbers of bricks in columns 0, 4 and 5 increase to 3.
There are 5 bricks in column 2 after phase 4.
Phase 5 removes all bricks from columns 6 and 7.
Input
First line consists of the two integers n and k (1 ≤ n ≤ 2 * 10^6, 1 ≤ k ≤ 5 *10^5). n is the number of columns of the wall, and k is the number of phases. Each of the next k lines has the format: op[i], left[i], right[i] and height[i]. op[i] is the type of phase i: 1 for an adding phase and 2 for a removing phase. The range of columns in phase i starts with column left[i] and ends with column right[i] (including both endpoints left[i] and right[i]). You will always have left[i] ≤ right[i]. height[i] is the height parameter of phase i.
Output
The output should consist of n integers, one per line, describing the result. Line i should describe the final number of bricks in column i (0 ≤ i ≤ n − 1).