Princess's Score Optimization

The princess has realized that her performance in the comprehensive subject is subpar, ranking over 1100 in a school of just 1100 students. After a long analysis, she concluded that by focusing solely on multiple-choice questions (for which the answers are derived from her estimated values for each question), she might do better. There are n questions numbered from 1 to n, and each question has an estimated value \(A_i\). She believes that the answer to a contiguous segment of questions lies between the \(\gcd\) and \(\mathrm{lcm}\) of their estimated values. Sometimes, her idea changes and some estimated values may get updated; other times, the answer to the multi‐select question (which asks for the number of options) equals the number of common divisors of the estimated values for that range.

In particular, you are given an integer sequence of length n and you have to process q operations of the following types:

• L x y p: Query the \(\mathrm{lcm}\) of the numbers in the segment \([x, y]\) and output its value modulo p.
• G x y p: Query the \(\gcd\) of the numbers in the segment \([x, y]\) and output its value modulo p.
• C x y c: Update the values of the numbers in the segment \([x, y]\) to be c.
• S x y p: Query the number of positive divisors (i.e. the count of common divisors) of the \(\gcd\) of the numbers in the segment \([x, y]\), and output this count modulo p.

Note: For \(\mathrm{lcm}\) of two numbers, you may use the formula \(\mathrm{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}\). To count the number of divisors of a number, a typical method is to iterate up to \(\sqrt{n}\) and count factors. Your task is to help the princess answer all queries so that she can secure a passing grade (and continue her OI training!).

inputFormat

The first line contains two integers n and q representing the number of questions and the number of operations, respectively.

The second line contains n integers \(A_1, A_2, \ldots, A_n\), the estimated values for each question.

The next q lines each contain an operation in one of the following formats:

• L x y p
• G x y p
• C x y c
• S x y p

It is guaranteed that all numbers are positive integers.

outputFormat

For each query of type L, G, or S, output the result on a new line in the order they appear in the input.

sample

5 5
2 3 4 5 6
L 1 3 100
G 2 5 100
S 1 5 100
C 3 4 10
G 1 5 50

12
1
1
1