Description

You are given a sequence of length $n$ with all initial values equal to $0$. You need to support the following two operations:

• Add $L, R, h$: For all elements in $[L, R]$ that are less than $h$, set them to $h$. Do not change elements whose height is greater than $h$.
• Remove $L, R, h$: For all elements in $[L, R]$ that are greater than $h$, set them to $h$. Do not change elements whose height is less than $h$.

You need to output the sequence after performing $k$ operations.

Input Format

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

Each of the next $k$ lines contains $4$ integers $t, L, R, h$. If $t = 1$, it denotes an Add operation; if $t = 2$, it denotes a Remove operation. The meanings of $L, R, h$ are as described above.

Output Format

Output $n$ lines. The integer on the $i$-th line is the value of the element with index $i - 1$ after all $k$ operations.

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

0
0
0
39412
39412
39412
48623
48623
48623
48623

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

3
4
5
4
3
3
0
0
1
0

Hint

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

Constraints: For all operations, the height $h$ satisfies $0 \leq h \leq 100\,000$.

Translated by ChatGPT 5