Now you have `N` lights in a line. Don't worry - the lights don't have color. The only status they have is on and off. And, each light has a value, too.

There is a boring student in ZJU. He decides to do some boring operations to the lights:

- Q
`L R status`- Query the GCD (Greatest Common Divisor) of the value of the given status lights in range [`L`,`R`]. For example, if now we have 3 lights which are {on, off and on}, and their value are {3, 5, 9}, then the GCD of the number of the lights on in [1, 3] is 3, and the lights off is 5. - I
`i value status`- Add a light just behind to`i`light. The initial status and the value is given also.^{th} - D
`i`- Remove the`i`^{th}light. - R
`i`- If`i`^{th}light is on, turn it off, else turn it on. - M
`i x`- Modify the value of`i`light to^{th}`x`.

Please help this boring guy to do this boring thing so that he can have time to find a girlfriend!

The input contains multiple test cases. Notice there's no empty line between each test case.

For each test case,
the first line of the a case contains two integers, `N` (1
≤ `N` ≤ 200000) and `Q` (1 ≤ `Q` ≤
100000), indicating the number of the lights at first and the number of
the operations.
In following `N` lines, each line contains two integers, `Num _{i}` (1 ≤

It is guaranteed that the range of the operations will be appropriate. For example, if there is only 10 lights, you will not receive an operation like "Q 1 11 0" or "D 11".

For each Query operation, output an integer, which is the answer to the query. If no lights are with such status, please output -1.

提交代码