Problem Description

There are $N$ desks numbered $1, 2, \ldots, N$ and $N$ containers numbered $1, 2, \ldots, N$. Multiple containers can be stacked on top of a desk.

Initially, container $i$ is placed on desk $i$.

You are given $Q$ queries to process in order. In the $i$-th query, move container $x_i$ and all containers stacked above it from desk $f_i$ to desk $t_i$ without changing their order.

If there are already containers on desk $t_i$, you must stack the moved containers on top of the existing ones, as illustrated in the following figure:

• This is an example for $f=1, t=2, x=4$. Move container $4$ and the container $2$ above it from desk $1$ to desk $2$.
• Since there are containers $3, 5$ already on desk $2$, you need to stack the moved containers on top of them.

After processing all $Q$ queries, determine which desk each container is on.

Input Format

The input is given from the standard input in the following format:

$N$ $Q$ $f_1$ $t_1$ $x_1$ $\vdots$ $f_{Q}$ $t_{Q}$ $x_{Q}$

Output Format

Output $N$ lines. The $i$-th line should contain the number of the desk where container $i$ is located.

Sample Input and Output

Sample Input #1

3 4
1 2 1
2 3 2
3 1 3
1 3 2

Sample Output #1

3
3
1

Sample Input #2

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

Sample Output #2

7
3
7
7
5
9
7
7
10
7

Notes/Hints

Notes

Discussion of this problem is prohibited until 2020/6/6 18:00 JST. If mentioned, legal action may be taken. It is okay to publish the total score or certification level after the exam, but please refrain from sharing information about which problems were solved.

Constraints

• All given inputs are integers.
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq f_i, t_i, x_i \leq N$
• $f_i \neq t_i$
• It is guaranteed that container $x_i$ is on desk $f_i$ at the time of processing the query.

Sample Explanation 1

• In the 1st query, move container $1$ from desk $1$ to desk $2$. Since there is container $2$ on desk $2$, stack container $1$ on top of it.
• In the 2nd query, move container $2$ and the container $1$ above it from desk $2$ to desk $3$. Since there is container $3$ on desk $3$, stack containers $2, 1$ on top of it.
• In the 3rd query, move container $3$ and the containers $2, 1$ above it from desk $3$ to desk $1$.
• In the 4th query, move container $2$ and the container $1$ above it from desk $1$ to desk $3$.
• Ultimately, containers $1, 2$ are on desk $3$ and container $3$ is on desk $1$.

见题面 Input 部分

见题面 Output 部分