Swaper#689
Before returning to headquarters, Aazu and Skive had to fill out a customs income declaration for their visit. This resulted in an impressive sequence of numbers. Processing this sequence took a long time.
– Swaper is curved, – the customs officer said knowingly.
– And what is a swaper? – asked a curious Skive.
Aazu explained that a swaper is a data structure that can do the following:
Take a segment of even length from to and swap the numbers with x + 1, x + 2 with x + 3, and so on;
Calculate the sum for any segment from to .
Since processing can take a long time, the "MYTH" corporation asked you to solve the swaper problem and simulate it efficiently.
Contains one or several tests. In the first line of each test, the length of the sequence and the number of operations (1 \leq n, m \leq 100000) are given. The second line contains integers not exceeding 10^6 by absolute value — the sequence itself. Then follow lines describing the queries: 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 and over all data does not exceed . The input is terminated by a line with two zeros. It is guaranteed that x_i < y_i, a_i \leq b_i.
For each test, output the answers to the queries of the second type as shown in the example. Separate the answers to different tests with a blank line.
Example 1