rev

Nargy şi Fumeanu joacă următorul joc: Nargy scrie pe o foaie şirul numerelor naturale de la $1$ la $N$, în ordine crescătoare. Apoi, face $M$ operaţii de forma: se iau doi indici $i$ şi $j$ şi se inversează bucata din şir aflată între poziţiile $i$ şi $j$. După fiecare operaţie, Nargy îl întreabă pe Fumeanu ce număr se află pe poziţia $k$.

Cerinţă

Scrieţi un program care îl ajută pe Fumeanu să răspundă la întrebările lui Nargy.

Date de intrare

Fişierul de intrare rev.in conţine pe prima linie două numere naturale $N \ M$. Următoarele $M$ linii vor conţine câte trei numere naturale $i \ j \ k$ cu semnificaţia de mai sus. Numerele de pe aceeaşi linie sunt separate prin spaţiu.

Date de ieșire

Fişierul de ieşire rev.out va conţine $M$ linii, câte o linie pentru fiecare operaţie din fişierul de intrare. Pe linia $i$ se va scrie numărul care se află pe poziţia $k$ în şir, după primele $i$ operaţii.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq M \leq 20 \ 000$
• Pentru $20\%$ dintre teste $N \leq 2 \ 000$ şi $M \leq 1 \ 000$
• Pentru $40\%$ din teste $M \leq 5 \ 000$

Exemplu

rev.in

7 3
1 3 2
4 6 5
2 5 3

rev.out

2
5
6

Explicație

• $\underline{1 \ 2 \ 3} \ 4 \ 5 \ 6 \ 7$
• $3 \ 2 \ 1 \ \underline{4 \ 5 \ 6} \ 7$
• $3 \ \underline{2 \ 1 \ 6 \ 5} \ 4 \ 7$
• $3 \ 5 \ 6 \ 1 \ 2 \ 4 \ 7$