Description

Original source: BZOJ 3211

The Flower God enjoys traveling on foot through various countries and dominating local programming competitions. The Flower God has a travel route that is linear, meaning all the countries visited are arranged in a straight line. The Flower God has a preference score for each country (though not necessarily liking all of them).

During each journey, the Flower God selects a segment of the route, which is a continuous sequence of countries. The happiness value of this journey is the sum of the preference scores of these countries. However, the Flower God's preference for these countries is not constant—sometimes, they may suddenly develop a dislike for certain countries, causing their preference score $\delta$ to change to $\sqrt \delta$ (perhaps because the Flower God has crushed the OI competitions in those countries and finds them boring).

Now, given the Flower God's travel route and changes in happiness, please calculate the happiness value for each journey.

Input Format

The first line contains an integer $N$, representing the number of countries;

The second line contains $N$ space-separated integers, representing the initial preference scores $\delta_i$ for each country;

The third line contains an integer $M$, representing the number of messages to process;

From the fourth line onwards, each line contains three integers $x, l, r$. When $x=1$, it queries the total happiness value for traveling from country $l$ to $r$, i.e., $\sum\limits_{i=l}^r \delta_i$. When $x=2$, the preference scores $\delta_i$ for countries $l$ to $r$ are changed to $\sqrt {\delta_i}$.

Output Format

For each query where $x=1$, output one integer per line, representing the happiness value of that journey.

Sample 1

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

101
11
11

Data Range and Hint

For all data, $1\le n\le 10^5,1\le m\le 2\times 10^5,1\le l\le r\le n,0\le \delta_i \le 10^9$.

Note: It is recommended to use the sqrt function with floor rounding.