P10463 Interval GCD

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.

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.

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

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