P4256 Princess #19 Prepares for the Monthly Exam

After finishing her games, the princess still has to take the monthly exam. (Even a princess has monthly exams, QWQ.)

The princess is very weak in liberal arts comprehensive, ranking $1100+$ in the whole school (and the whole school has just over $1100$ students). After thinking for a long time, she found that if she puts all her time into multiple-choice questions, she can score a bit better. There are $n$ questions in liberal arts, numbered from $1$ to $n$. The princess computed an estimated value $A_i$ for each question. She believes that the answer for a contiguous block of questions will lie between the $\gcd$ and $\operatorname{lcm}$ of their estimated values. Sometimes her thoughts change, and some questions’ estimated values will change. Sometimes multiple-answer questions appear; the number of correct answers for such questions equals the number of common divisors of the estimated values over a contiguous block. Specifically, for a sequence, there are four operations: - `L x y p`: Ask for the value of $\operatorname{lcm}$ of numbers in the range $[x,y]$ modulo $p$. - `G x y p`: Ask for the value of $\gcd$ of numbers in the range $[x,y]$ modulo $p$. - `C x y c`: Change all numbers in the range $[x,y]$ to $c$. - `S x y p`: Ask for the number of common divisors of the numbers in the range $[x,y]$, then take it modulo $p$. The princess must not fail the monthly exam, or she won't be able to study OI (just kidding), so please help her!

The first line contains two positive integers $n$ and $q$, where $n$ is the number of questions and $q$ is the number of operations. The second line contains $n$ positive integers, representing the princess’s estimated values for the questions. The next $q$ lines each contain one operation; see the Description for the format.

For each query, output its answer.

Constraints - For $30\%$ of the testdata, $1 \le n, q \le 1000$. - For another $20\%$ of the testdata, $1 \le n \le 1000$, $1 \le q \le 10^5$. - For another $20\%$ of the testdata, $1 \le n \le 10^5$, $1 \le q \le 10^5$, and there are no update operations. - For $100\%$ of the testdata, $1 \le n \le 3 \times 10^5$, $1 \le q \le 3 \times 10^5$. At any time, each question’s estimated value is in $[1, 100]$, and each answer after taking modulo fits in `int`. Translated by ChatGPT 5