Description

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!

Input Format

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.

Output Format

For each query, output its answer.

10 10
42 68 35 1 70 25 79 59 63 65 
L 2 6 28
L 2 6 43
G 2 7 5
G 3 4 83
L 7 9 96
G 2 7 39
S 3 8 100
L 4 5 12
G 4 4 65
L 2 4 69

0
32
1
1
75
1
1
10
1
34

Hint

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