Козак Вус və NCD#10447
Kozak Vus tam ədəddən ibarət massivini əldə etdi. Daha sonra ona massivinin də mövcud olduğu bildirildi, lakin Vus bu massivdə hansı ədədlərin olduğunu bilmir. massivini tapmaq üçün Kozak istədiyi qədər aşağıdakı əməliyyatdan istifadə edə bilər:
1 \leq l \leq r \leq n olan iki tam ədəd seçmək.
b_l + b_{l + 1} + \dots + b_r cəmini öyrənmək.
gcd(a_l, a_{l+1}, ..., a_r) qəpik ödəmək, burada ən böyük ortaq böləndir (məsələn, gcd(3, 5) = 1, və gcd(15, 30, 6) = 3).
Vus sizdən massivini tapmaq üçün lazım olan minimal qəpik sayını müəyyən etməyi xahiş edir.
Daha sonra Kozak dəfə müəyyən bir a_i ədədini ilə dəyişəcək. Hər belə dəyişiklikdən sonra yenilənmiş massiv üçün minimal qəpik sayını tapmaq lazımdır.
Birinci sətir və (1 \leq n \leq 10^5, 0 \leq q \leq 10^5) tam ədədlərini ehtiva edir — massivinin elementlərinin sayı və dəyişikliklərin sayı.
İkinci sətir tam ədəd a_1, a_2, ..., a_n (1 \leq a_i \leq 10^9) — massiv elementlərini ehtiva edir.
Növbəti sətir hər biri iki tam ədəd və (1 \leq i \leq n, 1 \leq x \leq 10^9) ehtiva edir — dəyişdirilən massiv elementinin indeksi və dəyişdirildiyi ədəd.
q + 1 ədəd çıxarın — massivinin hər versiyası üçün massivini tapmaq üçün lazım olan minimal qəpik sayını tapın.
Birinci ədəd — başlanğıc massivi üçün cavab.
Növbəti ədədlər — hər yenilənmə üçün cavablar.
Nümunə 1
Nümunə 2
( bal): n \le 10^2, q = 0;
( bal): n \le 10^3, q = 0;
( bal): q = 0;
( bal): q \leq 100;
( bal): q \leq 500;
( bal): q \leq 10000;
( bal): əlavə məhdudiyyətlər olmadan.