Fall FLASG | Solvable problem

Nici un om nu asterne in scris ceea ce are intentia sa spuna cu adevarat - sigma sigma boi, asta spune

Fie $V$ un sir de $N$ numere cuprinse in intervalul $[1, 1000]$. Spunem ca un interval $[l, r]$ din vector este bun daca indeplineste urmatoarele conditii:

• $r - l \geq 2$
• pentru oricare $l \leq i < j \leq r, \ \ j - i \geq 2$, exista un $c$ intre $i$ si $j$ ($i < c < j$) astfel incat $V_c = \dfrac{max(V_i,V_j)}{^† gcd(V_i,V_j)}$.

$^† gcd(a,b)$ = cel mai mare divizor comun al numerelor $a$ si $b$.

Cerință

Se dau $Q$ operatii de genul:

• $1 \ \ pos \ \ x \rightarrow a_{pos} = x$
• $2 \ \ l \ \ r \rightarrow$ afla cate intervale bune se afla in $[l,r]$.

Voi trebuie sa raspundeti la toate intrebarile de tipul $2$. Operatiile de tipul $1$ sunt permanente.

Date de intrare

Pe prima linie se afla doua numere naturale, $N$ si $Q$. Pe urmatoarea linie se afla vectorul $V$, urmat de $Q$ linii, reprezentand operatiile date.

Date de ieșire

Pe prima linie se va afisa $Nr$, numarul de intervale bune prezente in vectorul dat.
Ulterior se vor afisa, pe cate o linie separata, raspunsurile la intrebarile date.

Restricții și precizări

• $1 \leq N \leq 5 \cdot 10^5$;
• $1 \leq Q \leq 10^5$;
• Se garanteaza ca '$x$'-ul din cadrul operatiilor nu depaseste $1 \ \ 000$.

  #	Score	Constraints
  1	5	$Q = 0, N \leq 10$
  2	12	$Q = 0, N \leq 1 \ \ 000$
  3	23	$Q = 0$
  4	20	$Q \leq 100$
  5	12	$1 \leq N \leq 10^5$
  6	28	Fara restrictii

Exemplul 1

stdin

6 0 
3 1 1 1 2 2

stdout

2

Explicație

Doar intervalele $[2,4]$ si $[4,6]$ sunt bune.

Exemplul 2

stdin

10 8
1 1 1 1 1 1 1 1 1 1 
2 4 9
2 10 10
1 4 1
1 6 180
1 7 180
1 8 157
2 1 6
2 4 9

stdout

36
10
0
6
2