You are given an array A having n integers.

You have to perform some very hard queries on A.

There are 2 types of queries

- 1 id X, change A[id] with X.
- 2 L R, you have to find the minimum

number of steps required to change all elements in [L, R] such that

every element in [L, R] will have the odd number of divisors. In one step you can choose any element from A and can add or subtract 1 from it.

Note that in the second type of query, the array does not change.

**Input Format**

```
The 1st argument given is an integer array A.
The 2nd argument given is a 2D integer array B, where B[i] denotes ith query
```

**Output Format**

```
Return an Integer X % (1e9 + 7), the sum of answer for each query of type 2.
```

**Constraints**

```
1 <= N <= 100000
1 <= A[i], X <= 100000
1 <= number of queries <= 100000
1 <= id, L, R <= N
```

**For Example**

```
Input:
A = [1, 2, 3]
B = [[2, 1, 1], [2, 1, 2], [1, 3, 1], [2, 1, 3]]
Output:
2
Explanation:
query 1: we don't need any steps as 1 has an odd number of divisors, so the answer is 0.
query 2: in 1 step we can change 2 to 1, so the answer is 1.
query 3: change value of A[3] with 1, array after the 3rd query is A = [1, 2, 1]
query 4: again in 1 step we can change 2 to 1, so answer is 1.
So the sum of answers to all queries of type 2 is 2.
```

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**Very Hard Queries**

to access hints and editorial solutions for

Loading...