Description

We use a text processor to handle a special text file with $N$ lines. Each line contains exactly one natural number: the first line is $1$, the second line is $2$, and so on, up to line $N$ which is the natural number $N$.

A single "cut and paste" operation is defined as follows: first choose a consecutive block of lines. The "cut" operation removes the selected lines from the file, and the "paste" operation inserts the removed block into another position in the file.

Write a program to determine the contents of the first ten lines of the text file after performing several "cut and paste" operations in sequence.

Input Format

The first line contains two natural numbers $N$ and $K$, where $N$ is the total number of lines in the file $(10 \le N \le 100{,}000)$, and $K$ is the total number of "cut and paste" operations $(1 \le K \le 1000)$.

Each of the next $K$ lines describes one "cut and paste" operation with three space-separated natural numbers $A, B, C$, where $1 \le A \le B \le N$, $0 \le C \le N - (B - A + 1)$. $A$ and $B$ are the first and last line numbers of the selected block. $C$ is the line number immediately preceding the insertion position of the cut block; if $C = 0$, the block is inserted at the beginning of the file.

Output Format

Output ten lines, which are the numbers contained in the first ten lines of the text file after all operations have been completed.

13 3
6 12 1
2 9 0
10 13 8

6
7
8
9
10
11
12
2
3
4

Hint

Translated by ChatGPT 5