Problem Description

Recently, Slavko has been studying sequences of natural numbers. He finds a sequence interesting if the greatest common divisor (GCD) of all the elements in 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 Format

The first line of input contains the numbers N and Q (1 ≤ N, Q ≤ $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 ≤ $A_i$ ≤ $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 ≤ X ≤ N) and V (1 ≤ V ≤ $10^9$) from the task.
• If the query is of type 2, two numbers follow, L and R (1 ≤ L ≤ R ≤ N) that represent the left and right interval boundary.

Output Format

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

Sample Input and Output

Input Sample #1

5 1
8 4 3 9 1
2 2 5

Output Sample #1

4

Input Sample #2

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

Output Sample #2

6
1

Input Sample #3

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

Output Sample #3

10
5

Notes

Clarification of the first test case:

The interval from the 2nd to the 5th position consists of numbers (4, 3, 9, 1). In it, the following are interesting contiguous subarrays (denoted with square brackets):
[4] 3 9 1, 4 [3] 9 1, 4 3 [9] 1, 4 [3 9] 1

见题面 Input 部分

见题面 Output 部分