Bibble and Captain Snappy#4486
When Bibble and Captain Snappy don't know what to do, they play various interesting games. Today, Captain Snappy came up with a new game that, in his opinion, will help Bibble improve his arithmetic skills.
The rules of the game are simple: Captain Snappy takes wooden boards, numbers them from to , and writes some numbers on them. Then, he announces two numbers and , and Bibble must calculate the sum of all numbers on the boards numbered from to .
To prevent Bibble from memorizing all possible answers, Captain Snappy occasionally modifies the numbers. Specifically, he replaces all numbers in the range [l, r] with a sequence of numbers from to r - l + 1 in ascending order.
Bibble is not very good at arithmetic yet, so he asks you to write a program to help him perform these calculations.
The first line contains one integer (1 \le n \le 10^6) — the number of boards.
The second line contains integers — the initial values written on the boards (each number does not exceed 10^9).
The third line contains an integer (1 \le m \le 10^5) — the number of queries.
The next lines each describe one of two types of queries. The first number in each line, (1 \le t \le 2), indicates the type of query:
If t = 1, it is followed by two numbers and . You need to compute the sum of all numbers on the boards numbered from to .
If t = 2, it is followed by two numbers and . This means that the numbers on the boards numbered from to are replaced with the sequence 1, 2, \ldots, r - l + 1.
It is guaranteed that all queries are valid, and board numbering starts from .
For each query of type , print one number — the sum of values on the boards in the given range [l, r].
Example 1