oglinda

Pentru un număr natural $N$ se consideră șirul $a = (1, 2, 3, ..., N)$, deci $a_i = i$ pentru orice $i$, $1 ≤ i ≤ N$.
Asupra acestui șir se pot aplica operații de două tipuri:

1. La operația de tipul 1 se specifică două valori $i$ și $j$, cu $1 ≤ i ≤ j ≤ N$. Efectul acestei operații asupra șirului este de oglindire a secvenței din șir care începe cu elementul de pe poziția $i$ și se termină cu cel de pe poziția $j$. De exemplu, dacă în șirul $a = (1, 2, 3, 4, 5, 6, 7)$ se aplică operația $3 \ 6$, atunci șirul devine $a = (1, 2, 6, 5, 4, 3, 7)$. Iar în șirul $a = (1, 4, 3, 2, 5, 6, 7)$, dacă se aplică operația $4 \ 6$, atunci $a = (1, 4, 3, 6, 5, 2, 7)$.
2. Operația de tipul 2 conține un indice $i$, $1 ≤ i ≤ N$, și cere să afișăm valoarea elementului care se află în acel moment pe poziția $i$ în șir.

Se consideră $M$ astfel de operații într-o ordine dată.

Cerința

Scrieți un program care să determine și să afișeze rezultatul pentru fiecare operație de tipul $2$.

Date de intrare

Fișierul de intrare oglinda.in conține pe prima linie două numere naturale $N$ și $M$, separate printr-un spațiu. Pe fiecare dintre următoarele $M$ linii este specificată câte o operație de tipul $1$ sau $2$. O linie poate să conțină două sau trei numere, astfel: 1 i j (indicând o operație de tipul $1$) respectiv 2 i (indicând o operație de tip $2$). Valorile de pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire oglinda.out conține un număr de linii egal cu numărul de operații de tipul $2$ care sunt definite în fișierul de intrare. Pe fiecare linie este afișat câte un număr natural reprezintând rezultatul pentru o operație de tip $2$ prezentă în fișierul de intrare, în ordinea în care acestea sunt definite.

Restricții și precizări

• $1 ≤ N ≤ 1 \ 000 \ 000$
• $1 ≤ M ≤ 2 \ 000$
• Pentru teste în valoare de $40$ de puncte, vom avea $1 ≤ N ≤ 2 \ 000$.
• Se garantează că $1 ≤ i ≤ j ≤ N$ la operațiile de tipul $1$ și că $1 ≤ i ≤ N$ la operațiile de tip $2$.
• Se garantează că există cel puțin o operație de tipul $2$.

Exemplu

oglinda.in

10 4
2 3
1 2 7
2 3
2 1

oglinda.out

3
6
1

Explicație

Șirul inițial este: $1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10$
Rezultatul operației $2 \ 3$ are ca efect afișarea elementului de pe poziția $3$ (care este chiar 3).
Rezultatul operației $1 \ 2 \ 7$ are ca efect transformarea șirului în: $1 \ 7 \ 6 \ 5 \ 4 \ 3 \ 2 \ 8 \ 9 \ 10$.
Rezultatul operației $2 \ 3$ are ca efect afișarea elementului de pe poziția $3$ (care acum este $6$).
Rezultatul operației $2 \ 1$ are ca efect afișarea elementului de pe poziția $1$ (care acum are valoarea $1$).