Sequence Update and GCD Query

You are given an array \(a\) of length \(N\) and \(M\) operations. There are two kinds of operations:

1. C l r d: For each index \(i\) such that \(l \le i \le r\), add \(d\) to \(a_i\).
2. Q l r: Query the greatest common divisor (\(\gcd\)) of \(a_l, a_{l+1}, \dots, a_r\).

For each query operation, output an integer representing the answer.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\), separated by spaces.

The following \(M\) lines each describe an operation in one of the following formats:

• C l r d — add \(d\) to each element in the range \(a_l, a_{l+1}, \dots, a_r\).
• Q l r — query the \(\gcd\) of the subarray \(a_l, a_{l+1}, \dots, a_r\).

outputFormat

For each query operation, output a single line with one integer — the \(\gcd\) of the specified subarray. The answer should be non-negative.

sample

5 5
2 6 8 3 9
Q 1 5
C 2 4 3
Q 2 3
C 1 5 -2
Q 3 5

1
1
1