Distinct Values

Time Limit: 5 Seconds

Memory Limit: 131072 KB

Description

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

None

Source

None

提交代码