Jaca je pametna maca i za vas ima veoma jednostavan zadatak. Ona će vam dati prirodne brojeve ~N~ i ~Q~, nakon čega vi treba da napravite niz ~a = [1,2,\ldots,N]~ (niz se indeksira od ~1~) i da izvršite ~Q~ njenih naredbi. Svaka naredba ima jedan od sledeća dva oblika:

• ~1~ ~u~ ~v~ ~l~ - Za svako ~i \in \{0,1,\ldots,l-1\}~ (tim redom), izvršiti naredbu dodele ~a_{u+i} \leftarrow a_{v+i}~ (~a_{u+i}~ dobija vrednost koju u tom trenutku ima ~a_{v+i}~)
• ~2~ ~x~ - Recite Jaci trenutnu vrednost ~a_x~

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se prirodni brojevi ~N~ - veličina niza i ~Q~ - broj upita. Narednih ~Q~ linija mogu biti oblika ~1~ ~u~ ~v~ ~l~ ili ~2~ ~x~. U prvom slučaju važi ~u,v \geq 1~ i ~u+l-1,v+l-1\leq N~, a u drugom ~1 \leq x \leq N~.

Opis izlaza

Za svaki upit tipa ~2~ u poseban red standardnog izlaza ispisati traženi broj.

Primer 1

Ulaz

6 4
1 1 5 1
2 1
1 3 1 4
2 6

Izlaz

5
2

Objašnjenje primera

Nakon prve izmene niz će izgledati ovako: ~[5,2,3,4,5,6]~, u drugom upitu Jaca nam traži da joj kažemo ~a_1~, što iznosi ~5~. Nakon druge izmene (treći upit) niz će izgledati ovako: ~[5,2,5,2,5,2]~. U četvrtom upitu Jaca nas pita za ~a_6~, što iznosi ~2~.

Ograničenja

• ~N \leq 1.000.000, Q \leq 100.000~

Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 10 poena: ~N, Q \leq 5.000~
• U test primerima vrednim 30 poena: Svi upiti tipa ~2~ se nalaze posle svih upita tipa ~1~
• U test primerima vrednim 30 poena: U upitima tipa ~1~ važi ~|u-v| \geq l~
• U test primerima vrednim 30 poena: Nema dodatnih ograničenja