Cut&Paste

Să considerăm un fişier constituit din $N$ linii, pe fiecare linie fiind câte un număr natural. Iniţial, pe linia $1$ se află valoarea $1$, pe linia $2$ valoarea $2$, ş.a.m.d., pe linia $N$ se află valoarea $N$.

Fişierul iniţial a fost modificat cu ajutorul unui editor de texte, prin efectuarea a $M$ operaţii de tip cut&paste. O operaţie cut&paste constă în selectarea unui grup de linii consecutive, eliminarea lor din poziţia iniţială şi inserarea lor într-o altă poziţie în document.

Cerinţă

Scrieţi un program care, pentru o secvenţă de operaţii cut&paste dată, determină conţinutul primelor $10$ linii din fişierul obţinut după efectuarea operaţiilor.

Date de intrare

Pe prima linie a fișierului de intrare cutpaste.in se găsesc două numere întregi, $N$ și $M$. Pe următoarele $M$ linii se află triplete de forma $l_i \ r_i \ p_i$, unde $l_i$ și $r_i$ sunt capetele intervalului ales și $p_i$ este poziția după care inserăm valorile.

Date de ieșire

Fișierul de ieșire cutpaste.out va conține $10$ linii, linia $i$ conținând valoarea de pe poziția $i$ în șirul final.

Restricții și precizări

• $10 \leq N \leq 100 \ 000$;
• $1 \leq M \leq 1 \ 000$;
• Dacă $p_i = 0$, atunci inserăm la începutul documentului.

Exemplul 1

cutpaste.in

15 1
1 15 0

cutpaste.out

1
2
3
4
5
6
7
8
9
10

Exemplul 2

cutpaste.in

13 3
6 12 1
2 9 0
10 13 8

cutpaste.out

6
7
8
9
10
11
12
2
3
4

Exemplul 3

cutpaste.in

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

cutpaste.out

801
802
803
804
101
102
36
37
38
39