eolymp
bolt
Try our new interface for solving problems
Problems

Cheburashka and Crocodile Gena

Cheburashka and Crocodile Gena

Time limit 1 second
Memory limit 128 MiB

When Cheburashka and Crocodile Gena nothing to do, they play different interesting games. Today, Gena came up with a new game, which, in his opinion, will help Cheburashka to learn arithmetic. The rules of the game are very simple: Gena takes n tablets, numbers them from 1 to n and writes on them any numbers. Then he will say two numbers l and r, and Cheburashka must calculate the sum of all the numbers on the tablets numbered from l to r.

So that Cheburashka will not learn all the possible answers, Gena sometimes changes some numbers on the other, namely, all the numbers in the interval [l, r]. He does not want to think much, so just writes on these tablets the numbers from 1 to r - l + 1 in order. Cheburashka is not very well in arithmetic, so he asks you to write a program that will help him in this problem.

Input data

The first line contains the number of tablets n~(1 \le n \le 10^6). The next line contains n integers — the initial values on the tablets (all numbers do not exceed 10^9). Next given the number of queries m~(1 \le m \le 10^5). Then goes m lines, the first number in a string is a type of the query t~(1 \le t \le 2).

  • If t = 1, then given two integers l and r. You must calculate the sum of all the numbers on the tablets numbered from l to r;

  • If t = 2, then given two integers l and r. It means that on the tablets with numbers from l to r now will be values from 1 to r - l + 1 correspondingly.

It is guaranteed that query segments are usually correct. The numbering of tablets starts from one.

Output data

For each query with number 1 print the sum of numbers on a segment [l, r].

Examples

Input example #1
5
5 3 2 4 5
5
1 1 5
1 2 3
2 1 5
2 2 5
1 1 5
Output example #1
19
5
11
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013