# 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

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,10 ^{5}]**.

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

**1 i v** ** -** Set the value of

**i**element to

^{th}**v**.

**2 l r**

**Print the value of the function.**

*-***Constraints:****1 ≤ n ≤ 10 ^{5}**

**1 ≤ q ≤ 10**

^{5}**1 ≤ i ≤ n**

**1 ≤ v ≤ 10**

^{5}**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 |

91% Solution Ratio

Gias_UddinEarliest,

prodip_bsmrstuFastest, 0.0s

sagar1230Lightest, 2.0 MB

FrdhsnShortest, 1073B

Login to submit