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.

Input data

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.

Output data

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.

Examples

PASTE.IN

15 1
1 15 0

PASTE.OUT

1
2
3
4
5
6
7
8
9
10
PASTE.IN

13 3
6 12 1
2 9 0
10 13 8

PASTE.OUT

6
7
8
9
10
11
12
2
3
4
PASTE.IN

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

PASTE.OUT

801
802
803
804
101
102
36
37
38
39