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.

phase	type	range	height
0	add	columns $1$ to $8$	$4$
1	remove	columns $4$ to $9$	$1$
2	remove	columns $3$ to $6$	$5$
3	add	columns $0$ to $5$	$3$
4	add	columns $2$	$5$
5	remove	columns $6$ to $7$	$0$

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$.

Given the description of the $k$ phases, please calculate the number of bricks in each column after all phases are finished.

Input Specification

• Line $1$ of input consists of the two integers $n$, and $k$. $n$ is the number of columns of the wall, and $k$ is the number of phases.
• Line $2+i$ of input each consists of the format: $op[i],left[i],right[i],\text{ and }height[i]$.
  • $op[i]$ is the type of phase $i$: $1$ for an adding phase and $2$ for a removing phase, for $0\le i\le k-1$.
  • 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]$), for $0\le i\le k-1$. You will always have $left[i]\le right[i]$.
  • $height[i]$ is the height parameter of phase $i$, for $0\le i\le k-1$.

Output Specification

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$, for $0\le i\le n-1$.

Sample Input 1

10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

Sample Output 1

0
0
0
39412
39412
39412
48623
48623
48623
48623

Sample Input 2

10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

Sample Output 2

3
4
5
4
3
3
0
0
1
0

Subtasks

For all subtasks the height parameters of all phases are nonnegative integers less or equal to $100000$.

subtask	points	$n$	$k$	note
1	8	$1\le n\le 10000$	$1\le k\le 5000$	no additional limits
2	24	$1\le n\le 100000$	$1\le k\le 500000$	all adding phases are before all removing phases
3	29	$1\le n\le 100000$	$1\le k\le 500000$	no additional limits
4	39	$1\le n\le 2000000$	$1\le k\le 500000$	no additional limits