Uygun Sevkiyatlar#13104

Uygun Sevkiyatlar

9 saniye
256 megabayt

Bir yük istasyonunun ana hattında vagondan oluşan bir tren durmaktadır. Vagonlar lokomotiften başlayarak 'den 'ye kadar numaralandırılmıştır ve -inci vagon a_i adet özdeş kutu taşımaktadır.

İstasyon yükü sevkiyatlar hâlinde gönderir. Bir sevkiyat, ardışık i, i+1, \ldots, j vagonlarından oluşan bir gruptur ve bu grubun bütün kutuları konteynerlere paketlenir. Bir sevkiyat için kullanılan tüm konteynerlerin kapasitesi aynı d \ge 2 olmalıdır ve her vagon artık kalmadan tamamen paketlenmelidir. Ardışık vagonlardan oluşan bir grup, tek bir sevkiyat olarak gönderilebiliyorsa, yani grubun her vagonundaki kutu sayısı 'ye bölünecek şekilde bir d \ge 2 tam sayısı varsa, uygun olarak adlandırılır. Başka bir deyişle, grup ancak ve ancak \gcd(a_i, a_{i+1}, \ldots, a_j) > 1 ise uygundur. a_i \ge 2 kutu taşıyan tek bir vagon uygun bir grup oluşturur; tam olarak bir kutu taşıyan bir vagon ise oluşturmaz.

Gün boyunca iki türde toplam mesaj gelir:

İkinci türden tüm mesajları yanıtlayın.

Giriş

İlk satırda bir tam sayı (1 \le t \le 3 \cdot 10^5) — test durumlarının sayısı verilir.

Her test durumunun ilk satırında iki tam sayı ve (1 \le n, q \le 3 \cdot 10^5) — vagonların sayısı ve mesajların sayısı verilir. İkinci satırda tam sayı a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — kutuların başlangıçtaki sayıları verilir.

Sonraki satırın her biri iki biçimden birinde bir mesaj içerir:

  • 1 p x (1 \le p \le n, 1 \le x \le 10^9);

  • 2 l r (1 \le l \le r \le n).

Tüm test durumları üzerinden değerlerinin toplamı 3 \cdot 10^5'i, tüm test durumları üzerinden değerlerinin toplamı ise 3 \cdot 10^5'i aşmaz.

Çıktı

İkinci türden her mesaj için ayrı bir satırda bir tam sayı — verilen aralığın içindeki uygun grupların sayısını yazdırın. Yanıtları mesajların verildiği sırayla, test durumu test durumu ardından olacak şekilde yazdırın.

Örnekler

Örnek 1

Loading
Loading

Not

Şekilde birinci test durumu gösterilmektedir: iki 2 1 5 mesajı için her uygun grup, kendi vagonlarının altında bir çubuk olarak çizilmiştir.

Birinci test durumunda tren başlangıçta 2, 6, 3, 1, 4 şeklindedir. 'den 'ye kadar olan vagon grubu olarak yazılır.

  • 2 1 5 mesajı: uygun gruplar , , , , , olduğundan yanıt 'dır. Örneğin, uygun değildir çünkü \gcd(2, 6, 3) = 1, ve uygun değildir çünkü numaralı vagon bir kutu taşımaktadır.

  • 2 2 3 mesajı: uygun gruplar , , olduğundan yanıt 'tür.

  • 1 4 8 mesajı: tren 2, 6, 3, 8, 4 hâline gelir.

  • 2 1 5 mesajı: uygun gruplar , , , , , , , olduğundan yanıt 'dir.

  • 2 3 5 mesajı: uygun gruplar , , , olduğundan yanıt 'tür.

İkinci test durumunda tren 2, 2, 3, 3 şeklindedir.

  • 2 1 4 mesajı: uygun gruplar , , , , , olduğundan yanıt 'dır. ve numaralı vagonların ikisini birden içeren hiçbir grup uygun değildir, çünkü \gcd(2, 3) = 1.

  • 2 2 3 mesajı: uygun gruplar ve olduğundan yanıt 'dir.

Üçüncü test durumunda tren şeklindedir.

  • 2 1 1 mesajı: tek vagon bir kutu taşımaktadır, bu yüzden uygun grup yoktur ve yanıt 'dır.