Rivalry Friends

Ryo and his girlfriend love to think about challenges. One day his girlfriend gave him a challenge to solve a problem. She gave him a function named RivalryFriends.

The function counts the number of integers between 1 and n inclusive, which are relatively prime to n, i.e. the numbers whose highest common factor with n is 1. RivalryFriends(1) is defined to be 1. Examples:

RivalryFriends(5) = 4
RivalryFriends(6) = 2 

Here, {1, 2, 3, 4} are relatively prime to 5. So RivalryFriends(5) = 4.

Similarly, {1, 5} are relatively prime to 6. Hence RivalryFriends(6) = 2.

Now, Ryo has to calculate the function, RivalryFriends for any n. As Ryo is very talented, he easily solved the problem. So Ryo and his girlfriend thought of making a new problem with a twist for you. Now you will be given an integer array A[] of size n and q queries to perform on the array. The queries will be:

Query type 1: Set the value of the i'th element to v, i.e. A[i] = v. This type of query appears in the input in 1 i v format.

Query type 2: Print the value of the function given below:

$ \sum\limits_{i=l}^{r}{RivalryFriends(A[i])} $

This second type of query appears in the input in 2 l r format.

Input

The first line of input contains two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 105).

The next line will contain n space separated integers in the range [1, 105].

Each of the next q lines contains a task in one of the following form:

1 i v: Set the value of ith (1 ≤ i ≤ n) element to v (1 ≤ v ≤ 105).

2 l r: Print the value of the function. (1 ≤ l ≤ r ≤ n)

Output

For each query of type 2, print the value of the function.

Sample

Input	Output
3 3 1 2 3 2 1 3 1 3 5 2 1 3	4 6