Again Alice and Bob is playing a game with stones. There are N piles of stones labelled from 11 to NN, the ii th pile has aiai stones.
First Alice will choose piles of stones with consecutive labels, whose leftmost is labelled with LL and the rightmost one is RR. After, Bob will choose another consecutive piles labelled from ll to rr(L≤l≤r≤R)(L≤l≤r≤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 ii th and i+1i+1 pile have aiai and ai+1ai+1 stones respectively, after this swapping there will be ai+1ai+1 and aiai.
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
Input contains several test cases.
For each case:
The fisrt line contains NN, MM. NN is mentioned aboved ans MM is the number of the sum of game rounds and the times of Bob's swapping.
The second line contains N integars a1,a2,...ana1,a2,...an, indicating the number of each piles' stones.
The next M lines will have an integar optopt(1≤opt≤2)(1≤opt≤2), indicating the type of operation.
If opt equals 11, then LL and RR follow. Alice and Bob start a new round and Alice choose LL and RR as mentioned.
If opt equals 22, then POSPOS follows. Bob will swap the piles labelled POSPOS and POS+1POS+1.