ip

Termenii de iscoditură și primeneală sunt minunate cuvinte arhaice pe care le utiliza și Ștefan cel Mare. Azi, olimpicii noștri utilizează în locul lor cuvinte englezești: query și update.

Ștefan Vodă, după bătălia de la Vaslui, și-a aliniat cei $n$ oșteni și a dat fiecăruia câte un număr natural nenul $a_0$, $a_1, \dots a_{n-1}$. Având o bună dispoziție după strașnica victorie, voievodul face două tipuri de operații:

• $1$ $i$ $x$ (aceasta este primeneala!): oșteanul de la poziția $i$ primește o nouă valoare ($a_i$ devine egal cu $x$);
• $2$ $x$ $y$ $d$ (aceasta este iscoditura!): câte numere din secvența de oșteni $a_x, a_{x+1}, \dots a_y$ au cel mult $d$ divizori?

Cerință

Scrieți un program care răspunde corect la toate iscoditurile și veți fi la fel de faimoși ca Ștefan cel Mare!

Date de intrare

Fișierul de intrare ip.in conține pe prima linie numărul natural $n$, pe a doua linie numerele $a_0, a_1, \dots a_{n-1}$, separate prin câte un spațiu, iar pe a treia linie numărul natural $m$, reprezentând numărul de operații. Pe fiecare dintre următoarele $m$ linii se află fie o primeneală, dată prin trei numere de forma $1$ $i$ $x$, fie o iscoditură, dată prin patru numere $2$ $x$ $y$ $d$.

Date de ieșire

Fișierul de ieșire ip.out conține atâtea linii câte iscodituri sunt. Linia $i$ conține răspunsul la a $i$-a iscoditură.

Restricții și precizări

• $4 \leq n, m \leq 122 \ 500$;
• $1 \leq a_i \leq 200 \ 000$, pentru orice $0 \leq i \leq n - 1$;
• Pentru fiecare primeneală de forma $1$ $i$ $x$, $0 \leq i < n$, $1 \leq x \leq 200 \ 000$;
• Pentru fiecare iscoditură de forma $2$ $x$ $y$ $d$, $0 \leq x \leq y < n$, $1 \leq d \leq 200 \ 000$.

Exemplu

ip.in

6
12 3 5 10 1 16
4
2 0 5 3
1 4 24
2 2 4 7
2 1 4 1

ip.out

3
2
0

Explicație

Prima iscoditură $2$ $0$ $5$ $3$ cere să se determine câte numere din întreg șirul au cel mult $3$ divizori.

Răspunsul este $3$, aceste numere fiind $3$, $5$ și $1$.

După primeneala $1$ $4$ $24$ șirul devine $12$ $3$ $5$ $10$ $24$ $16$.

Pentru iscoditura $2$ $2$ $4$ $7$, se întreabă câte numere din secvența $5$ $10$ $24$ au cel mult $7$ divizori și răspunsul este $2$, aceste numere fiind $5$ și $10$.

Pentru iscoditura $2$ $1$ $4$ $1$, se întreabă câte numere din secvența $3$ $5$ $10$ $24$ au cel mult un divizor și răspunsul este $0$.