Problem Description

Given a sequence of length $n$ initialized with all values as $0$. You need to support the following two operations:

• Add $L, R, h$: Set all elements in the range $[L, R]$ to $h$ if their current value is less than $h$, without changing elements whose values are greater than $h$.
• Remove $L, R, h$: Set all elements in the range $[L, R]$ to $h$ if their current value is greater than $h$, without changing elements whose values are less than $h$.

You are required to output the sequence after performing $k$ such operations.

Input Format

The first line of input contains two positive integers $n$ and $k$, representing the number of elements in the sequence and the number of operations, respectively. Note: the sequence indices are numbered from $0$ to $n-1$.

The next $k$ lines each contain four integers $t, L, R, h$. If $t = 1$, it indicates an Add operation; if $t = 2$, it indicates a Remove operation. The meanings of $L, R, h$ are as described in the problem statement.

Output Format

The output consists of $n$ lines, each containing one integer. The $i$-th line represents the value of the element at index $i - 1$ in the sequence after $k$ operations.

Sample Input and Output

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

Notes

• Subtask #1 (8 points): Satisfies $1 \leq n \leq 10,000, 1 \leq k \leq 5,000$;
• Subtask #2 (24 points): Satisfies $1 \leq n \leq 100,000, 1 \leq k \leq 500,000$, with all Add operations occurring before all Remove operations;
• Subtask #3 (29 points): Satisfies $1 \leq n \leq 100,000, 1 \leq k \leq 500,000$;
• Subtask #4 (39 points): Satisfies $1 \leq n \leq 2,000,000, 1 \leq k \leq 500,000$.

All operation heights $h$ satisfy $0 \leq h \leq 100,000$.

见题面 Input 部分

见题面 Output 部分