Lately, Slavko's been studying sequences of natural numbers. He finds a sequence interesting if the greatest common divisor of all the elements from the sequence is greater than 1.

Yesterday, he found a sequence consisting of $N$ natural numbers in his garage. Since he was really bored, he decided to keep himself occupied by asking simple queries. Each query can be one of the two types:

1. Change the value at position $X$ in the sequence to $V$.
2. Determine the number of interesting contiguous subarrays contained in the interval [L, R] of the sequence.

Input Specification

The first line of input contains the numbers $N$ and $Q$ $(1\le N,Q\le {10}^5)$, representing the number of elements in the sequence and the number of queries, respectively.

The following line contains $N$ natural numbers $A_i$ $(1\le A_i\le {10}^9)$ that represent the numbers in the initial sequence.

Each of the following $Q$ lines contains a query of the following form:

• The first number in the line can be 1 or 2 and represents the type of the query.
• If the query is of type 1, two numbers follow, $X$ $(1\le X\le N)$ and $V$ $(1\le V\le {10}^9)$ from the task.
• If the query is of type 2, two numbers follow, $L$ and $R$ $(1\le L\le R\le N)$ that represent the left and right interval boundary.

Output Specification

For each query of type 2, output the number of interesting contiguous subarrays from the task.

Sample Input 1

5 1
8 4 3 9 1
2 2 5

Sample Output 1

4

Sample Input 2

5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5

Sample Output 2

6
1

Sample Input 3

4 3
2 2 2 2
2 1 4
1 2 3
2 1 4

Sample Output 3

10
5