U jednom gradu postoji metro-linija sa N stanica, numerisanih brojevima od 1 do N. Metro ide pravolinijski, tj. sa stanice broj i možemo metroom doći do stanica broj i - 1 i i + 1 (sa stanice 1 možemo doći samo do stanice 2 a sa stanice N samo do stanice N -1). Svaka stanica ima svoj ulazni kod - jedan prirodan broj koji se menja svakog dana. Ako imamo kartu sa rednim brojem k, mi možemo doći na neku stanicu (sa leve ili desne strane) samo ako k deli ulazni kod te stanice. Nas zanima koliko stanica možemo posetiti za različite početne stanice i različite brojeve karata.

Preciznije, dato je Q upita jednog od sledeća dva tipa:

• 1 i x - promeniti ulazni kod i-te stanice na x,

• 2 i k - ispisati koliko stanica možemo posetiti ako smo trenutno u i-toj i imamo kartu sa rednim brojem k.

  Odgovoriti na sve upite tipa 2. Broj naše karte će uvek deliti ulazni kod početne stanice.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalaze se dva prirodna broja, N i Q, koji predstavljaju, redom, broj stanica i broj upita (1 ≤ N ≤ 200.000, 1 ≤ Q ≤ 100.000). Sledeći red sadrži N prirodnih brojeva manjih od 2 ·10⁹ - početne ulazne kodove. Sledićih Q redova sadrže upite u gore opisanom formatu (izvršavaju se u datom redosledu). Za svaki od upita važi 1 ≤ i ≤ N, 2 ≤ k, x ≤ 2· 10⁹.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) Za svaki upit tipa 2 ispisati odgovor (ceo broj) u posebnom redu izlazne datoteke. Na upite odgovarati u datom redosledu.

Primer 1:

6 4
2 25 20 30 19 5
2 3 5
2 4 6
1 5 100
2 3 5

3
1
5

Objašnjenje.

Ako smo na stanici broj 3 (ulazni kod 20) i imamo kartu broj 5, mi možemo posetiti tri stanice - 2, 3 i 4. Iako 5 deli ulazni kod stanice broj 6, mi do nje ne možemo doći jer ne možemo ući na stanicu sa ulaznim kodom 19. U drugom upitu nalazimo se na stanici broj 4 i ne možemo nigde otići. Posle promene ulaznog koda stanice broj 5, mi iz stanice broj 3 sa kartom broj 5 možemo posetiti 5 stanica - 2, 3, 4, 5 i 6.

Napomena.

U 20% test primera Q ≤ 10³. U 40% test primera imamo uvek istu kartu tj. u svim upitima tipa 2 broj k će biti isti (u ovim primerima je Q neparno a u ostalim je parno).