Wall

Time limit3sMemory limit256 MB

Summary

Apply k range raise-to-at-least and lower-to-at-most updates on n columns and print each final height.

Level: Hard8 of 10
Topics: Segment tree
Solved: No attempts yet

Problem

Gianina builds a wall of $n$ columns of equal bricks. Columns are numbered $0$ through $n-1$ from left to right. The height of a column is its brick count.

Initially every column has height 0. Over $k$ steps, each step gives an inclusive column range $[\text{left}, \text{right}]$ and a height $h$ .

Add (op=1): within the range, any column shorter than $h$ receives bricks until its height is exactly $h$ . Columns already at least $h$ stay unchanged.
Remove (op=2): within the range, any column taller than $h$ loses bricks until its height is exactly $h$ . Columns already at most $h$ stay unchanged.

After all steps, output the final brick count in each column.

Input

Line 1: $n$ , $k$ .

Next $k$ lines: op left right height

op=1 add, op=2 remove
left, right: inclusive range ( $0 \le \text{left} \le \text{right} < n$ )
height: target height

Output

Print the final brick count of each column, one per line from left to right.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
5 1
1 0 4 2
```
Expected output
```
2
2
2
2
2
```
Example 3
Input
```
3 2
1 0 2 5
2 1 1 3
```
Expected output
```
5
3
5
```

Example 4

Input

10 2
1 0 9 10
2 0 9 0

Expected output

Example 5
Input
```
1 2
1 0 0 7
1 0 0 3
```
Expected output
```
7
```
Example 6
Input
```
5 3
1 0 4 1
1 0 4 3
2 0 4 2
```
Expected output
```
2
2
2
2
2
```