Cut and Paste

Time limit1sMemory limit128 MB

Summary

Simulate K cut-and-paste block moves on an N-line document and report the first ten resulting line values.

Level: Medium5 of 10
Topics: Simulation, Array, Implementation
Solved: No attempts yet

Problem

A document produced by a text editor consists of $N$ lines. Initially the first line contains the number $1$ , the second line contains the number $2$ , and so on, so that the $i$ -th line contains the number $i$ (for $1 \le i \le N$ ).

Exactly $K$ "cut and paste" operations are then performed on the document. Each operation acts on a group of consecutive lines: the "cut" removes the selected lines from the document, and the "paste" reinserts the removed block at another position among the remaining lines.

Given the sequence of "cut and paste" operations, determine the contents of the first ten lines of the document after all operations have been performed.

Input

The first line contains two integers $N$ and $K$ separated by a space: the number of lines in the document ( $10 \le N \le 100{,}000$ ) and the number of "cut and paste" operations ( $1 \le K \le 1{,}000$ ).

Each of the next $K$ lines describes one operation, in the order in which they are executed, as three integers $A$ , $B$ , and $C$ separated by spaces, where $1 \le A \le B \le N$ and $0 \le C \le N - (B - A + 1)$ . Here $A$ and $B$ are the first and last lines of the block to be cut, numbered within the current document, and $C$ is the line, counted in the document after the block has been removed, after which the block must be inserted. If $C = 0$ , the block is inserted at the very beginning of the document.

Output

Print ten lines containing the numbers written on the first ten lines of the document after all operations have been performed.

Examples3

Example 1
Input
```
15 1
1 15 0
```
Expected output
```
1
2
3
4
5
6
7
8
9
10
```

Example 2

Input

Expected output

Example 3

Input

Expected output