Game

Again Alice and Bob is playing a game with stones. There are N piles of stones labelled from $1$ to $N$, the $i$ th pile has $a_i$ stones.

First Alice will choose piles of stones with consecutive labels, whose leftmost is labelled with $L$ and the rightmost one is $R$. After, Bob will choose another consecutive piles labelled from $l$ to $r$ $(L \leq{l}\leq{r}\leq R)$. Then they're going to play game within these piles.

Here's the rules of the game: Alice takes first and the two will take turn to make a move: choose one pile with nonegetive stones and take at least one stone and at most all away. One who cant make a move will lose.

Bob thinks this game is not so intersting because Alice always take first. So they add a new rule, which is that Bob can swap the number of two adjacent piles' stones whenever he want before a new round. That is to say, if the $i$ th and $i + 1$ pile have $a_i$ and $a_{i + 1}$ stones respectively, after this swapping there will be $a_{i + 1}$ and $a_i$.

Before today's game with Bob, Alice wants to know, if both they play game optimally when she choose the piles from L to R, there are how many pairs (l, r) chosed by Bob that will make Alice *win*.

Input contains several test cases.

For each case:

The fisrt line contains $N$, $M$. $N$ is mentioned aboved ans $M$ is the number of the sum of game rounds and the times of Bob's swapping.

The second line contains N integars $a_1, a_2, ... a_n$, indicating the number of each piles' stones.

The next M lines will have an integar $opt$ $(1 \leq opt \leq 2)$, indicating the type of operation.

If opt equals $1$, then $L$ and $R$ follow. Alice and Bob start a new round and Alice choose $L$ and $R$ as mentioned.

If opt equals $2$, then $POS$ follows. Bob will swap the piles labelled $POS$ and $POS + 1$.


$0 \leq a_i \leq 1,000,000$

$1 \leq N, M \leq 100,000, \sum{N}, \sum{M} < 600,000$

$1 \leq L \leq R \leq N$

$1 \leq POS < N$

For each case:

For each opt which equals $1$, you shall output one line with an integar indicating the number of pairs $(l, r)$ that will make Alice win the round.

3 3
4 0 4
2 2
2 1
1 1 3

3

2019 Multi-University Training Contest 3