Codah ClubВежбај. Пошаљи. Напредуј.
Пријави се
Српски
#000608

Metro

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.


InputU prvom redu standardnog ulaza 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^9 - 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^9.

OutputZa svaki upit tipa 2 ispisati odgovor (ceo broj) u posebnom redu standardnog izlaza. Na upite odgovarati u datom redosledu.

Primer:
6 4
2 25 20 30 19 5
2 3 5
2 4 6
1 5 100
2 3 5
Izlaz:
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 ≤ 1.000. 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).

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.