Art Class

Interview

Time limit0.5sMemory limit512 MB

Summary

Given N cells and Q range queries that paint only still-uncolored cells, print the final color of each cell.

Level: Medium4 of 10
Topics: Union-find, Array
Solved: No attempts yet

Problem

Minkyu suddenly wanted to draw one day. Nearby, Jeonghwan, who has mastered both art and competitive programming, was solving a problem. Minkyu asked Jeonghwan how to draw well, and Jeonghwan handed him a long rectangular sheet of uncolored paper with $N$ cells. He said that a beautiful picture would be finished if Minkyu followed these instructions:

a b x: paint every uncolored cell from the $a$ -th to the $b$ -th cell with color $x$ .

However, Minkyu finds this process too tedious and wants someone else to do it. Let's complete Minkyu's drawing for him.

Input

The first line contains the number of cells $N$ and the number of queries $Q$ , separated by a space ( $1 \le N \le 10^5$ , $1 \le Q \le 10^5$ ). Each of the next $Q$ lines contains one query ( $1 \le a \le b \le N$ , $1 \le x \le 10^9$ ).

Output

After all queries are performed, print the color of each cell on one line, separated by spaces. Cells that were never painted are printed as $0$ .

Examples1

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