is doing a contest. He comes across the following problem:
You have an array of elements, indexed from to . There are operations you need to perform on it.
Each operation is one of the following:
C x vChange the -th element of the array to .
M l rOutput the minimum of all the elements from the -th to the -th index, inclusive.
G l rOutput the greatest common divisor of all the elements from the -th to the -th index, inclusive.
Q l rLet be the result of the operation
G l rright now. Output the number of elements from the -th to the -th index, inclusive, that are equal to .
At any time, every element in the array is between and (inclusive).
knows that one fast solution uses a Segment Tree. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?
The first line has and .
The second line has integers, the original array.
The next lines each contain an operation in the format described above.
Q operation, output the answer on its own 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