逆序对
题号：NC222132
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

我们称逆序对为一个序列中满足 且 的二元组 。

若一个排列的逆序对个数为奇数，则称它为一个奇排列，否则它被称为偶排列。

给出一个长度为 的排列，有 种操作：

  •  交换 和 。
  •  翻转区间 内的数。
  •  将区间 内的数左移 位。
  •  将区间 内的数右移 位。

对一个长度为 的序列的操作定义如下：

  • 翻转。对于所有 ，将第 个位置的数移动到第 个位置。
  • 左移 位。对于所有 ，将第 个位置的数移动到第 个位置，第 个位置的数移动到第 个位置。重复此操作 次。
  • 右移 位。对于所有 ，将第 个位置的数移动到第 个位置，第 个位置的数移动到第 个位置。重复此操作 次。

注意上述定义中同一个操作内的移动都是同时进行的。

小 想要知道每次操作之后这个排列是奇排列还是偶排列。



输入描述:

第一行两个整数 ，表示序列的长度和操作的次数。
第二行  个整数，表示一个  至  的排列。
接下来  行，每行三或四个整数，表示一次操作，具体格式及其含义见题目描述。

输出描述:

共  行表示每次操作后的答案，若为奇排列则输出 ，若为偶排列则输出 。
示例1

输入

复制 
5 5
1 2 3 4 5
1 1 3
1 2 3
2 2 5
3 1 2 1
4 3 5 1

输出

复制 
1
0
0
1
1

说明

原排列的逆序对个数为 。
第一次操作后序列为：，逆序对个数为 ，故输出 。
第二次操作后序列为：，逆序对个数为 ，故输出 。
第三次操作后序列为：，逆序对个数为 ，故输出 。
第四次操作后序列为：，逆序对个数为 ，故输出 。
第五次操作后序列为：，逆序对个数为 ，故输出 。
示例2

输入

复制 
10 10
1 4 3 5 2 9 8 6 7 10
1 2 3
2 3 5
4 3 7 2
2 3 5
3 5 7 4
1 2 6
4 1 10 6
3 2 4 3
1 3 4
2 3 9

输出

复制 
0
1
1
0
0
1
1
1
0
1

说明


备注:

对于前  的数据，，，保证  操作中 。 
对于前  的数据，，，保证  操作中 。 
对于前  的数据，，，保证  操作中 。 
对于另外  的数据，，，保证对于任意操作都有 。 
对于另外  的数据，，，保证输入中仅存在操作 。 
对于  的数据，，，。