Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Rivalry Friends

By AnikaTahsin · Limits 1s, 256 MB

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 and q . 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 element to v.
2 l r - Print the value of the function.

Constraints:
1 ≤ n ≤ 105
1 ≤ q ≤ 105
1 ≤ i ≤ n
1 ≤ v ≤ 105
1 ≤ l ≤ r ≤ n

Output

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

Sample

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


Discussion
Statistics

91% Solution Ratio

Gias_UddinEarliest, 1w ago

prodip_bsmrstuFastest, 0.0s

sagar1230Lightest, 2.0 MB

FrdhsnShortest, 1073B

Submit

Login to submit