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
1 ≤ N ≤ 100 000
1 ≤ M ≤ 20 000
Pentru 20% dintre teste N ≤ 2000 şi M ≤ 1000
Pentru 40% din teste M ≤ 5000
