Totient Query on Bank Deposits

On a beautiful continent there are 100,000 countries, numbered from 1 to 100,000. In each country there is a bank. Initially every bank holds a deposit of 3 dollars. However, the arithmetic on fortunes is unusual – the operation of "addition" is carried out as ordinary multiplication. In other words, if all banks start with 3 dollars then the total "sum" of wealth is 3¹⁰⁰⁰⁰⁰.

Only the first 60 primes are allowed as the "currency denominations":

\(p_1 = 2,\; p_2 = 3,\; p_3 = 5, \ldots, p_{60} = 281\)

A fortune (a positive integer) is always expressed as a product: \(fortune = p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_{60}^{k_{60}}\).

The leader of a large company, known for his extreme thrift, opens an account in every bank with a deposit of 3 dollars. From time to time he either instructs his subordinate GFS to count the total deposits in a consecutive range of banks or to update the deposit in a particular bank. When counting the deposits for a range [a, b] the leader computes the product of all deposits (let that product be \(P\)). Then he selects one of the banks among those in the range [1, P] for verification. However, he will never choose a bank whose number is "in conflict" with \(P\>.

A bank number \(number\) is considered to be not in conflict with \(P\) if and only if there exist integers \(x\) and \(y\) such that:

\(number \times x + P \times y = 1\)

This condition is equivalent to \(\gcd(number, P)=1\). Thus, the number of banks available for selection is \(\varphi(P)\), where \(\varphi(\cdot)\) is Euler's totient function. Recall that if \(P = \prod_{i=1}^{60} p_i^{e_i}\), then:

\(\varphi(P) = \prod_{i=1}^{60}\Big(p_i^{e_i-1} \times (p_i-1)\Big) \quad \text{(for those }e_i>0\text{)}\)

After some profits the leader sometimes updates a bank’s deposit (the new deposit is again a positive integer that can be factorized only using these 60 primes, and the total deposit will not exceed 10⁶). Given a series of operations (queries and updates) please help GFS determine, for each query, how many banks (modulo 19961993) can be chosen by the leader.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 100000, m ≥ 1), where n is the number of banks. The banks are initially numbered from 1 to n and every bank initially holds a deposit of 3.

The second line contains n integers representing the initial deposits (each deposit is a product of powers of the first 60 primes; initially they are all 3).

Each of the next m lines describes an operation in one of the following formats:

• Q a b – a query operation asking for the number of banks in the range [1, P] (modulo 19961993) that are not in conflict with \(P\), where \(P\) is the product of deposits in banks from index a to b (1-indexed).
• U pos val – an update operation that sets the deposit at bank pos to val (again, val is given in its decimal representation and can be factorized solely by the first 60 primes, and will not exceed 10⁶).

outputFormat

For each query operation, print on a new line the value of \(\varphi(P)\) modulo 19961993.

sample

5 5
3 3 3 3 3
Q 1 3
U 2 6
Q 1 3
U 5 30
Q 2 5

18
18
432

</p>