You have an array of ~N~ elements, indexed from ~1~ to ~N~. There are ~M~ operations you need to perform on it.

Each operation is one of the following:

• C x v change the ~x~-th element of the array to ~v~.
• M l r output the minimum of all elements between indicies ~l~ and ~r~, inclusive.
• G l r output the greatest common divisor of all elements between indicies ~l~ and ~r~, inclusive.
• Q l r let ~G~ be the result of G l r right now. Output the number of elements between indicies ~l~ and ~r~, inclusive, equal to ~G~.

Constraints

~1 \le N \le 10^5~

~1 \le M \le 5 \times 10^5~

At any time, every element in the array is between ~1~ and ~10^9~, inclusive.

Input Specification

The first line contains ~N~ and ~M~.

The second line contains ~N~ integer,s the original array.

The next ~M~ lines each contain an operation as described above.

Output Specification

For each M, G, and Q query, output the answer on a new 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