你需要帮珂朵莉维护一个长为 $n$ 的 01序列 $a$，有 $m$ 个操作：

• 1 l r：把区间 $[l,r]$ 的数变成 $0$。
• 2 l r：把区间 $[l,r]$ 的数变成 $1$。
• 3 l r：$[l,r-1]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i+1}$ 按位或的值，这些数同时进行这个操作。
• 4 l r：$[l+1,r]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i-1}$ 按位或的值，这些数同时进行这个操作。
• 5 l r：$[l,r-1]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i+1}$ 按位与的值，这些数同时进行这个操作。
• 6 l r：$[l+1,r]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i-1}$ 按位与的值，这些数同时进行这个操作。
• 7 l r：查询区间 $[l,r]$ 的和。

本题强制在线，每次的 $l,r$ 需要与上次答案做 $\operatorname{xor}$ 运算，如果之前没有询问，则上次答案为 $0$。

输入格式

第一行两个整数表示 $n$ 和 $m$。

第二行 $n$ 个整数表示序列 $a$。

之后 $m$ 行，每行三个整数 $opt,l,r$，表示是哪一种操作以及操作对应的区间。

输出格式

对于每个查询操作输出一行一个数表示答案。

样例数据

样例输入

5 5
0 1 0 0 1
3 2 5
5 2 5
2 2 2
6 1 5
7 1 5

样例输出

1

样例解释

序列每次的样子： $$0\ 1\ 0\ 0\ 1$$ $$0\ 1\ 0\ 1\ 1$$ $$0\ 0\ 0\ 1\ 1$$ $$0\ 1\ 0\ 1\ 1$$ $$0\ 0\ 0\ 0\ 1$$ $$0\ 0\ 0\ 0\ 1$$

子任务

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于 $30\%$ 的数据，$n,m\leq 1000$。

对于 $50\%$ 的数据，$n,m\leq 10^5$。

对于另外 $30\%$ 的数据，操作和序列均随机生成。

对于另外 $10\%$ 的数据，$n,m\leq 10^6$。

对于 $100\%$ 的数据，$1\leq n,m\leq 3 \times 10^6$，$0\leq a_i\leq 1$。