Dr. Euler is analyzing a data set. In his research, he encounters the following computational challenge:

You are given an array of \(\mathbf{N}\) (\(1 \leq \mathbf{N} \leq 100,000\)) elements, indexed from 1 to \(\mathbf{N}\). There are \(\mathbf{M}\) (\(1 \leq \mathbf{M} \leq 500,000\)) operations you need to perform on this array.

Each operation is one of the following:

• C x v: Modify the \(x\)-th element of the array to \(v\).
• M l r: Compute and output the minimum value of all the elements from the \(l\)-th to the \(r\)-th index, inclusive.
• G l r: Compute and output the greatest common divisor of all the elements from the \(l\)-th to the \(r\)-th index, inclusive.
• Q l r: Let \(G\) be the result of the operation \(G,\ l,\ r\) at this moment. Output the count of elements from the \(l\)-th to the \(r\)-th index, inclusive, that equate to \(G\).

At any given time, every element in the array is between 1 and \(10^9\) (inclusive).

Dr. Euler acknowledges that a swift solution would involve a Segment Tree. Despite his familiarity with this data structure, he struggles to implement it accurately. Can you provide a correct implementation.

Input Specification

The first line contains \(N\) and \(M\).

The second line presents NNN integers, representing the initial array.

The subsequent \(M\) lines each denote an operation as previously described. Output Specification

For each \(M\), \(G\), or \(Q\) operation, provide the answer on a separate line. Sample Input 1

5 5
1 1 4 2 8
C 2 16
M 2 4
G 2 3
C 2 1
Q 1 5

Sample Output 1

2
4
2

Sample Input 2

5 2
1 1 2 2 2
Q 1 4
Q 3 5

Sample Output 2

2
3