# 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 (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

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


### Statistics

90% Solution Ratio

Gias_UddinEarliest, 6M ago

sagar1230Lightest, 2.0 MB

Jarif_RahmanShortest, 889B