레이팅 미적용Lately, Slavko’s been studying sequences of natural numbers. He finds a sequence
interesting if the greatest common divisor of all the elements from the sequence is greater
than 1.
Yesterday, he found a sequence consisting of \(N\) natural numbers in his garage. Since he
was really bored, he decided to keep himself occupied by asking simple queries. Each query
can be one of the two types:
1.
Change the value at position \(X\) in the sequence to \(V\).
2.
Determine the number of interesting contiguous subarrays contained in the interval
[\(L\), \(R\)] of the sequence.
The first line of input contains the numbers \(N\) and \(Q\) (\(1 \le N\), \(Q \le 10^{5}\)), representing the
number of elements in the sequence and the number of queries, respectively.
The following line contains \(N\) natural numbers \(A_{i}\) (\(1 \le A_{i} \le 10^{9}\)) that represent the numbers in
the initial sequence.
Each of the following \(Q\) lines contains a query of the following form:
●
The first number in the line can be 1 or 2 and represents the type of the query.
●
If the query is of type 1, two numbers follow, \(X\) (\(1 \le X \le N\)) and \(V\) (\(1 \le V \le 10^{9}\)) from
the task.
●
If the query is of type 2, two numbers follow, \(L\) and \(R\) (\(1 \le L \le R \le N\)) that represent
the left and right interval boundary.
For each query of type 2, output the number of interesting contiguous subarrays from the
task.
5 1
8 4 3 9 1
2 2 5
4
5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5
6
1
4 3
2 2 2 2
2 1 4
1 2 3
2 1 4
10
5