3417 - Below The Root

Created by Luis Manuel Díaz Barón
Added by luismo (2015-11-23)
Limits
Total Time: 8000 MS | Test Time: 2000 MS |Memory: 512 MB | Output: 64 MB | Size: 9 KB
Enabled languages
Available in

Description

Once you bought your cellphone with Android, you realized that you wanted to become a developer, by the time you had a certain level developing apps, you found out that you needed to get Super User access into your phone’s operative system, so you needed to “root” it. To achieve you goal, your cellphone will put you through an easy task.
You will be given an array of N (1 <= N <= 10^5) integers randomly generated between 1 and 10^9 and you will perform Q (1 <= Q <= 10^5) queries on it:
Query 1: Given an interval [i, j], with i and j between 1 and N you will reduce to its square root each of the array inside this interval. Is the resulting value is not an integer you will truncate it.
Query 2: Given two integers i and v, you will change the value at position i by v.
Query 3: Given an interval [i, j], with i and j between 1 and N you will print the sum of the values of the array inside this interval.
Once you finish the task correctly you will get Super User access in your phone.

Once you bought your cellphone with Android, you realized that you wanted to become a developer, by the time you had a certain level developing apps, you found out that you needed to get Super User access into your phone’s operative system, so you needed to “root” it. To achieve you goal, your cellphone will put you through an easy task.
You will be given an array of N (1 <= N <= 10^5) integers randomly generated between 1 and 10^9 and you will perform Q (1 <= Q <= 10^5) queries on it:
Query 1: Given an interval [i, j], with i and j between 1 and N you will reduce to its square root each of the array inside this interval. Is the resulting value is not an integer you will truncate it.
Query 2: Given two integers i and v, you will change the value at position i by v.
Query 3: Given an interval [i, j], with i and j between 1 and N you will print the sum of the values of the array inside this interval.
Once you finish the task correctly you will get Super User access in your phone.

Once you bought your cellphone with Android, you realized that you wanted to become a developer, by the time you had a certain level developing apps, you found out that you needed to get Super User access into your phone’s operative system, so you needed to “root” it. To achieve you goal, your cellphone will put you through an easy task.
You will be given an array of N (1 <= N <= 10^5) integers randomly generated between 1 and 10^9 and you will perform Q (1 <= Q <= 10^5) queries on it:
Query 1: Given an interval [i, j], with i and j between 1 and N you will reduce to its square root each of the array inside this interval. Is the resulting value is not an integer you will truncate it.
Query 2: Given two integers i and v, you will change the value at position i by v.
Query 3: Given an interval [i, j], with i and j between 1 and N you will print the sum of the values of the array inside this interval.
Once you finish the task correctly you will get Super User access in your phone.

Input specification

In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query

In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query

In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query

Output specification

For each query of type 3 print the asked value

;jsessionid=0BC73C1E8A63C4F2CD2B9A63385962F9

For each query of type 3 print the asked value

;jsessionid=0BC73C1E8A63C4F2CD2B9A63385962F9
In the first line two space separated integers N (1 <= N <= 10^5) and Q (1 <= Q <= 10^5)
The second line contains N spaced separated integers, the values of the randomly generated array
The next Q lines contain three space separated integers representing the description of a single query in the format below:
1 i j – for the first query
2 i v – for the first query
3 i j – for the first query

Sample input

6 5
4 3 3 4 5 8
1 1 4
2 3 5
3 1 6
1 3 5
3 4 6

Sample output

23
11

Hint(s)

Cambiar los jds que tienen a > b en la query
Cambiar los jds que tienen a > b en la query
Cambiar los jds que tienen a > b en la query