E. Своппер

Своппер — структура, которая умеет две вещи: взять отрезок и поменять местами $a_x$ с $a_{x+1}$, $a_{x+2}$ с $a_{x+3}$, и так далее; и посчитать сумму на произвольном отрезке.

Все обмены выровнены: первый индекс отрезка нечётный, последний чётный. Значит, пары $(1,2), (3,4), (5,6), \ldots$ — одни и те же для всех операций.

В первой строке $n$ и $m$ ($1 \le n, m \le 2 \cdot 10^5$). Во второй строке $n$ чисел $a_i$ ($|a_i| \le 10^6$).

В следующих $m$ строках операции. 1 x y — обменять по парам на отрезке $[x, y]$; гарантируется, что $x$ нечётно, $y$ чётно и $x < y \le n$. 2 l r — сумма на отрезке ($1 \le l \le r \le n$).

Для каждой операции второго вида выведите сумму в отдельной строке.