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 a0, a1, … an-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 (ai devine egal cu x);
• 2 x y d (aceasta este iscoditura!): câte numere din secvența de oșteni ax, ax+1, …, ay au cel mult d divizori?

Cerința

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 a0, a1, … an-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 va 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 ≤ n, m ≤ 122.500
• 1 ≤ ai ≤ 200.000, pentru orice 0 ≤ i ≤ n - 1.
• Pentru fiecare primeneală de forma 1 i x, 0 ≤ i < n, 1 ≤ x ≤ 200.000
• Pentru fiecare iscoditură de forma 2 x y d, 0 ≤ x ≤ y < n, 1 ≤ d ≤ 200.000
• Pentru 17 puncte, toate iscoditurile vor avea d ≤ 9
• Pentru 17 puncte, toate operațiile sunt de tip iscoditură.
• Pentru 13 puncte, 4 ≤ n, m ≤ 1.000
• Pentru 53 de puncte, fără restricții suplimentare

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.