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 106 by absolute value - the sequence itself. Next m lines describe the the queries in the form 1xiyi - query of the first type and 2aibi - 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 xi < yi, ai ≤ bi.

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.