Dat je niz od n brojeva. Nad nizom se izvršavaju, jedan za drugim, m upita jednog od sledeća dva tipa:

• 1 i - seče trenutni niz posle i-tog elementa i zatim drugi deo niza (od (i + 1)-vog elementa do kraja) stavlja na početak, pri čemu se dobija novi niz od n elemenata. Npr. za niz 5 3 10 8 8, upit '1 2' daje 5 3 | 10 8 8 → 10 8 8 | 5 3 → 10 8 8 5 3.

• 2 j - treba odgovoriti koji se broj nalazi na j-toj poziciji u trenutnom nizu.

  Odgovoriti na sve upite tipa 2.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalaze se 2 prirodna broja n i m koji predstavljaju, redom, broj elemenata niza i broj upita (1 ≤ n, m ≤ 10⁵). Sledeći red sadrži n celih brojeva - elemente niza u datom redosledu (svi elementi su iz [0, 10⁹]). Sledećih m redova sadrže upite već opisanog formata: 'a b' gde je a ∈ {1, 2} i 1 ≤ b ≤ n. Upiti se izvršavaju u redosledu datim na ulazu.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) Za svaki upit tipa 2 iz ulazne datoteke ispisati u novi red izlazne datoteke odgovor na taj upit (odgovore ispisivati u odgovarajućem redosledu). Postojaće bar jedan upit tipa 2.

Primer:

5 4
5 3 10 8 8
2 3
1 2
1 4
2 3

10
8

Objašnjenje.

Na trećoj poziciji u početnom nizu je broj 10. Posle dva sećenja niz postaje 3 10 8 8 5. Na trećoj poziciji u ovom nizu je broj 8.

Napomena.

U 30% test primera biće n, m ≤ 10³.