# 3412. Swaps and Sum

You are given a sequence $a_1, a_2, \dots, a_n$. The task is to perform the following queries on it:

• Type 1. Given two integers $l$ and $r$ . Reorder the elements of the sequence in such a way (changed part of the sequence is in brackets):
$$a_1, a_2, \dots, a_n \Rightarrow a_1, a_2, \dots, a_{l-2}, a_{l-1}, [a_{l+1}, a_l, a_{l+3}, a_{l+2}, \dots, a_r, a_{r-1}], a_{r+1}, a_{r+2}, \dots , a_n$$
That is swap the first two elements of segment $[l,r]$, the second two elements, and so on.

• Type 2. Given two integers $l$ and $r$, print the value of sum $\sum_{ i = l }^{ r } a_i$.

### 输入格式

The first line contains two integers $n$ and $q$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$, denoting initial sequence.

Each of the next $q$ lines contains three integers $tp_i, l_i, r_i$, where $tp_i$ denotes the type of the query, and $l_i$ are $r_i$ parameters of the query. It’s guaranteed that for a first-type query $r-l+1$ will be even.

• $2 \leq n \leq 2 \times 10^5$
• $1 \leq q \leq 2 \times 10^5$
• $1 \leq a_i \leq 10^6$
• $1 \leq tp_i \leq 2$
• $1 \leq l_i \leq r_i \leq n$

### 输出格式

For each query of the second type print the required sum.

### 样例

Input
6 4
1 2 3 4 5 6
1 2 5
2 2 3
2 3 4
2 4 5
Output
5
7
9

1 人解决，5 人已尝试。

1 份提交通过，共有 7 份提交。

9.9 EMB 奖励。