Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3918
Distinct Values

Time Limit: 10 Seconds      Memory Limit: 131072 KB

You are given a sequence {A0, A1, ..., AN-1}. Defined a function called G(L, R) on A, where G(L, R) = GCD(Ai) (Li < R) that is the greatest common divisor of all the integers in the subsequence.

Now there're two kinds of question for you:

  1. M i v: Set the value of Ai to v. (0 ≤ i < N, 1 ≤ v ≤ 100)
  2. C L R: Consider all possible values of i and j that Li < jR, and calculate how many unique values of G(i, j) there will be. (0 ≤ L < RN)

Input

There are multiple test cases. Each case begin with a line contains two integers N and Q (1 ≤ N, Q ≤ 10000). The next line contains N integers, A0, A1, ..., AN-1 (1 ≤ Ai ≤ 100). The next Q lines each contains one of two kinds of question mentioned above.

Output

For each C question output an integer in a separate line.

Sample Input

2 3
4 6
C 0 2
C 0 1
C 1 2

Sample Output

3
1
1

Hint

Huge input and output, scanf and printf is recommended.


Author: LIN, Xi
Source: ZOJ Monthly, February 2016
Submit    Status