Swaper
Before returning to headquarters Aazu and Skive had to fill up on local customs the declaration of income for the visit. The result was a rather impressive sequence of numbers. Processing this sequence took a very long time.
– Swaper is curved - with knowledge of the matter said the customs officer.
– And what is a swaper? – asked a curious Skiff.
Aahz explained that swaper is a data structure that is able to do the following:
take a segment of even length from x to y and swap the numbers x and x + 1, x + 2 and x + 3, and so on;
calculate the sum at any segment from a to b.
Knowing that accounting can take a long time, the corporation "myth" asked you to solve the problem with swaper and simulate it efficiently.
Input
Contains multiple test cases. The first line contains the sequence length n and the number of operations m (1 ≤ n, m ≤ 100000). Second line contains n integers, not exceeding 10^6 by absolute value - the sequence itself. Next m lines describe the the queries in the form 1 x[i] y[i] - query of the first type and 2 a[i] b[i] - query of the second type. The sum of all n and m in all input data does not exceed 200000. Input is terminated with a line of two zeros. It is guaranteed that x[i] < y[i], a[i] ≤ b[i].
Output
For each test case write the answers to the questions of the second type, as shown in the example. Separate answers to tests by a blank line.