Masala #MLSCOZO58N

Xotira 256 MB Vaqt 4000 ms
14

EKUB so'rovlar

Otabek yaqinda natural sonlar ketma-ketligini o'rganishni boshladi. U quyidagi shartni qondiradigan qism ketma-ketlikni qiziqarli deb hisoblaydi: qism ketma-ketlikdagi barcha elementlarining eng katta umumiy bo'luvchisi 1 dan katta bo'lishi kerak.

Kecha Otabek o'zining garajida N ta natural sonlardan iborat ketma-ketlikni topdi. U juda zerikkanligi sababli, o'zi uchun oddiy savollarni bera boshladi. Har bir savol ikki turdan biriga tegishli:

  1. X-pozitsiyadagi elementni V qiymatiga o'zgartirish.
  2. Ketma-ketlikning [L, R] intervalida joylashgan qiziqarli qism ketma-ketliklar sonini aniqlash.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va Q musbat butun sonlari – ketma-ketlikdagi elementlar soni va so'rovlar soni beriladi. Keyingi qatorda N ta natural son \(A_i\) ketma-ketlikning elementlari sifatida keltirilgan. Keyingi Q qatorda har biri quyidagi shakldagi so'rovlar berilgan:

  • Agar so'rov turi 1 bo'lsa, X va V sonlari beriladi, bu holda X -pozitsiyadagi elementning qiymati V ga o'zgartiriladi.
  • Agar so'rov turi 2 bo'lsa, L va R sonlari beriladi, bu holda ketma-ketlikning L dan R gacha bo'lgan qiziqarli qism ketma-ketliklar sonini topish kerak.

\(1 \le N, Q \le 10^5\)

\(1 \le X \le N\)

\(1 \le A_i, V_i \le 10^9\)


Chiquvchi ma'lumotlar:

Har bir 2-turdagi so'rov uchun, ketma-ketlikning qiziqarli bo'laklar sonini alohida qatorda chop eting.


Misollar
# input.txt output.txt
1
5 1
8 4 3 9 1
2 2 5
4
2
5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5
6
1
3
4 3
2 2 2 2
2 1 4
1 2 3
2 1 4
10
5