Urns and Balls
Description
Consider $n$ different urns and $n$ different balls. Initially, there is one ball in each urn.
There is a special device designed to move the balls. Using this device is simple. First, you choose a range of consecutive urns. The device then lifts all the balls from these urns. After that, you specify a destination which is another range of urns having the same length. The device then moves the lifted balls and places them in the destination urns. Each urn can contain any number of balls.
Given a sequence of movements for this device, determine where each of the balls will be placed after all these movements.
The first line contains two integers $n$ and $m$, representing the number of urns and the number of movements ($1 \le n \le 100\,000$, $1 \le m \le 50\,000$). Each of the next $m$ lines contains three integers $count_i$, $from_i$ and $to_i$ indicating thet the device simultaneously moves all balls from urn $from_i$ to urn $to_i$, all balls from $from_i + 1$ to urn $to_i + 1$, $\ldots$, all balls from urn $from_i + count_i - 1$ to urn $to_i + count_i - 1$ ($1 \le count_i, from_i, to_i \le n$, $\max(from_i, to_i) + count_i \le n + 1$).
Output exactly $n$ numbers from $1$ to $n$: the final positions of all balls. The first number represents the final position of the ball that was initially in urn $1$, the second number represents the final position of the ball from urn $2$, and so on.
Input
The first line contains two integers $n$ and $m$, representing the number of urns and the number of movements ($1 \le n \le 100\,000$, $1 \le m \le 50\,000$). Each of the next $m$ lines contains three integers $count_i$, $from_i$ and $to_i$ indicating thet the device simultaneously moves all balls from urn $from_i$ to urn $to_i$, all balls from $from_i + 1$ to urn $to_i + 1$, $\ldots$, all balls from urn $from_i + count_i - 1$ to urn $to_i + count_i - 1$ ($1 \le count_i, from_i, to_i \le n$, $\max(from_i, to_i) + count_i \le n + 1$).
Output
Output exactly $n$ numbers from $1$ to $n$: the final positions of all balls. The first number represents the final position of the ball that was initially in urn $1$, the second number represents the final position of the ball from urn $2$, and so on.
2 3
1 1 2
1 2 1
1 2 1
10 3
1 9 2
3 7 3
8 3 1
1 1
1 2 1 2 3 4 1 2 2 8