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