Əlverişli göndərişlər#13104

Əlverişli göndərişlər

9 saniyə
256 meqabayt

Yük stansiyasının əsas yolunda vaqondan ibarət qatar dayanıb. Vaqonlar lokomotivdən başlayaraq -dən -ə qədər nömrələnib və -ci vaqon a_i eyni qutu daşıyır.

Stansiya yükü göndərişlərlə yola salır. Göndəriş — bu, ardıcıl i, i+1, \ldots, j vaqonlarından ibarət qrupdur və onun bütün qutuları konteynerlərə yığılır. Bir göndəriş üçün istifadə olunan bütün konteynerlərin tutumu eyni d \ge 2 olmalıdır və hər vaqon qalıqsız, tam şəkildə yığılmalıdır. Ardıcıl vaqonlardan ibarət qrup, əgər onu bir göndəriş kimi yola salmaq mümkündürsə, yəni elə tam d \ge 2 ədədi varsa ki, qrupun hər vaqonundakı qutuların sayı -yə bölünür, əlverişli adlanır. Başqa sözlə, qrup yalnız və yalnız o halda əlverişlidir ki, \gcd(a_i, a_{i+1}, \ldots, a_j) > 1. a_i \ge 2 qutu daşıyan tək vaqon əlverişli qrup təşkil edir; dəqiq bir qutu daşıyan vaqon isə yox.

Gün ərzində iki növdən olan mesaj daxil olur:

İkinci növdən olan bütün mesajlara cavab verin.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 3 \cdot 10^5) — test hallarının sayı verilir.

Hər test halının birinci sətrində iki tam ədəd və (1 \le n, q \le 3 \cdot 10^5) — vaqonların sayı və mesajların sayı verilir. İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — qutuların ilkin sayları verilir.

Növbəti sətrin hər biri iki formadan birində mesaj ehtiva edir:

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

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

Bütün test halları üzrə -lərin cəmi 3 \cdot 10^5-i, bütün test halları üzrə -ların cəmi isə 3 \cdot 10^5-i aşmır.

Çıxış

İkinci növdən olan hər mesaj üçün ayrıca sətirdə bir tam ədəd — verilmiş parçanın daxilindəki əlverişli qrupların sayını çap edin. Cavabları mesajların verildiyi ardıcıllıqla, test halı ardınca test halı olmaqla çap edin.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Şəkildə birinci test halı göstərilib: iki 2 1 5 mesajı üçün hər əlverişli qrup öz vaqonlarının altında zolaq şəklində təsvir olunub.

Birinci test halında qatar əvvəlcə 2, 6, 3, 1, 4 şəklindədir. -dən -ə qədər vaqonlar qrupu kimi yazılır.

  • 2 1 5 mesajı: əlverişli qruplar , , , , , -dir, deməli cavab -dır. Məsələn, əlverişli deyil, çünki \gcd(2, 6, 3) = 1, və əlverişli deyil, çünki -cü vaqon bir qutu daşıyır.

  • 2 2 3 mesajı: əlverişli qruplar , , -dür, deməli cavab -dür.

  • 1 4 8 mesajı: qatar 2, 6, 3, 8, 4 şəklini alır.

  • 2 1 5 mesajı: əlverişli qruplar , , , , , , , -dir, deməli cavab -dir.

  • 2 3 5 mesajı: əlverişli qruplar , , , -dir, deməli cavab -dür.

İkinci test halında qatar 2, 2, 3, 3 şəklindədir.

  • 2 1 4 mesajı: əlverişli qruplar , , , , , -dür, deməli cavab -dır. və vaqonlarının hər ikisini ehtiva edən heç bir qrup əlverişli deyil, çünki \gcd(2, 3) = 1.

  • 2 2 3 mesajı: əlverişli qruplar və -dür, deməli cavab -dir.

Üçüncü test halında qatar şəklindədir.

  • 2 1 1 mesajı: yeganə vaqon bir qutu daşıyır, buna görə də əlverişli qrup yoxdur və cavab -dır.