Problem Description

Given an array $a$ of length $N$ and $M$ instructions, each instruction is one of the following two types:

1. C l r d, meaning to add $d$ to all of $a_l, a_{l+1}, \dots, a_r$.
2. Q l r, meaning to query the greatest common divisor ($\gcd$) of $a_l, a_{l+1}, \dots, a_r$.

For each query, output one integer as the answer.

Input Format

The first line contains two integers $N, M$.

The second line contains $N$ integers, representing $a_1, a_2, \dots, a_N$.

The next $M$ lines describe the $M$ instructions. The format of each instruction is the same as in the description.

Output Format

For each query, output one integer as the answer, one per line.

5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4

1
2
4

Hint

For $100\%$ of the testdata: $N \le 5\times10^5$, $M \le 10^5$, $1 \le a_i \le 10^{18}$, $|d| \le 10^{18}$. It is guaranteed that during computation, the values will not exceed the range of long long.

Translated by ChatGPT 5