시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111100.000%

문제

A document processed by a text processor consists of N lines of text. The first line contains number 1, the second line contains number 2 and so on till the Nth line which contains number N.

Exactly M operations 'cut and paste' have been performed in that document. It operates on a selected group of consecutive lines; 'cut' removes selected text from the document and 'paste' inserts removed text elsewhere in the rest of the document.

Write a program that will for given sequence of  'cut and paste' operations determine the contents of the first ten lines of final document after all operations have been performed.

입력

The first line of input file contains two natural numbers N, number of lines in a document (10 ≤ N ≤ 100,000) and K, number of operations 'cut and paste' performed on a document (1 ≤ K ≤ 1000), separated by a space character.

Next K lines contain information of 'cut and paste' operations in the order of their execution. 

Each line contain three natural numbers A, B and C, 1 ≤ A ≤ B ≤ N, 0 ≤ C ≤ N-(B-A+1), separated by a space character. Numbers A and B determine first and last line of selected text, and number C determines the line after which the removed text should be inserted. If C equals 0 then removed test should be inserted at the beginning of the document.

출력

The output file should consist of 10 lines containing the numbers written in the first 10 lines of final document after all operations have been performed.

예제 입력 1

15 1
1 15 0

예제 출력 1

1
2
3
4
5
6
7
8
9
10

예제 입력 2

13 3
6 12 1
2 9 0
10 13 8

예제 출력 2

6
7
8
9
10
11
12
2
3
4

예제 입력 3

1000 6
3 7 4
1 100 57
50 60 200
63 70 500
1 800 4
7 77 98

예제 출력 3

801
802
803
804
101
102
36
37
38
39