Description

"The first minute, X said, let there be a sequence, so a sequence of positive integers was given.

The second minute, L said, it should be modifiable, so there was an operation that takes the floor of the square root of every number in a segment.

The third minute, k said, it should be queryable, so there was an operation to find the sum of a segment.

The fourth minute, Caihong Miao said, make it NOIP difficulty, so there were constraints.

The fifth minute, the poet said, let there be rhythm, so there were time and memory limits.

The sixth minute, He Xue said, save some trouble, so it was guaranteed that during computation and in the final result, all values fit within the representable range of a $64$-bit signed integer type.

The seventh minute, this problem was finally created, but the problem setters no longer wanted to write the program for it."

— "Seven Minutes to Make a Problem · Part II"

So this sacred task is handed to you.

Input Format

The first line contains an integer $n$, the number of elements in the sequence.

The second line contains $n$ positive integers, the initial sequence.

The third line contains an integer $m$, the number of operations.

Each of the next $m$ lines contains three integers k l r.

• $k=0$ means replace every number in $[l,r]$ with the floor of its square root.
• $k=1$ means query the sum of the numbers in $[l,r]$.

It is possible in the testdata that $l>r$, so when this happens please swap $l$ and $r$.

Output Format

For each query operation, output one answer per line.

10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

19
7
6

Hint

Constraints:

• For 30% of the testdata, $1\le n,m\le 10^3$, and the numbers in the sequence do not exceed $32767$.
• For 100% of the testdata, $1\le n,m\le 10^5$, $1\le l,r\le n$, the numbers in the sequence are greater than $0$ and do not exceed $10^{12}$.

Translated by ChatGPT 5