[yLOI2020] 泸沽寻梦

> 我应是泸沽烟水里的过客， > 孑然弹铗，划天地开阖。 > 邂逅过的，梦醒之余， > 却忘了该如何洒脱。 ——银临《泸沽寻梦》

> 南有仙地，名曰摩梭，摩梭有湖，泸沽是也。 茶茶在泸沽湖中寻找自己的梦。氤氲雾气中，茶茶的 $n$ 个梦排成了一个序列。茶茶的所有梦境都是拉瓦的样子。为了区分这些拉瓦，茶茶规定从左到右第 $i$ 个的拉瓦的美颜值是一个非负整数 $a_i$。面对着这些梦，茶茶会进行 $m$ 次操作，每次操作会给定两个数字 $p,x$，然后将 $a_p$ 和 $a_{p+1}$ 都对 $x$ 做按位异或。每次操作完之后，茶茶都想知道，当前的梦序列中，有多少个子区间 $[l,r]$，满足 $l \le r$ 且区间的异或和为 $0$，请你回答茶茶的问题。 区间 $[l,r]$ 的异或和定义为 $a_l \otimes a_{l + 1} \otimes \dots a_{r - 1} \otimes a_r$。其中 $\otimes$ 代表二进制按位异或运算，即 C++ 语言的「^」运算符。两个区间不同当且仅当两区间左端点不同或两区间右端点不同或两区间左右端点均不同。 为了避免输出过大，你只需要输出四个整数，分别表示你所有回答的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。

第一行有两个整数，分别表示梦境的数量 $n$ 和操作的次数 $m$。 第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数表示第 $i$ 个拉瓦的美颜值 $a_i$。 接下来 $m$ 行，每行两个整数，依次表示一次操作的 $p$ 和 $x$。

输出四行，每行一个整数，依次表示你所有回答的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。

5 3
1 2 3 4 5
1 3
2 3
3 3

3
3
3
1

### 样例 1 解释 - 第一次操作后，序列变为 ${2,1,3,4,5}$，有且仅有区间 $[1,3]$ 的异或和为 $0$，故本次询问的答案为 $1$。 - 第二次操作后，序列变为 ${2,2,0,4,5}$，区间 $[1,2]$、$[1,3]$、$[3,3]$ 的异或和为 $0$，故本次询问的答案为 $3$。 - 第三次操作后，序列变为 ${2,2,3,7,5}$，有且仅有区间 $[1,2]$ 的异或和为 $0$，故本次询问的答案为 $1$。所有答案的异或和为 $3$，有 $3$ 次回答的答案为奇数，所有答案中的最大值为 $3$，最小值为 $1$。 ### 数据规模与约定 **本题采用多测试点捆绑测试**，共有 5 个子任务。 - 子任务 $1$（$10$ 分）：保证 $n,m \le 100$。 - 子任务 $2$（$10$ 分）：保证 $n,m \le 300$。 - 子任务 $3$（$20$ 分）：保证 $n,m \le 3000$。 - 子任务 $4$（$30$ 分）：保证 $n,m \le 10^5$。 - 子任务 $5$（$30$ 分）：无特殊限制。 对于前四个子任务，保证 $a_i,x \le n$； 对于全部的测试点，保证 $1 \le n,m \le 10^6$，$0 \le a_i,x \le 10^9$，$1 \le p<n$。 ### 提示 - 请注意，$a_i,x \leq Y$ 不能说明 $a_i \otimes x \leq Y$。 - 请注意大量数据读入对程序效率造成的影响。 - 本题的特殊输出方式只是为了避免输出过大造成程序超时，与本题解法无关。 - 请注意常数因子对程序效率造成的影响。 - 本题共有两个样例文件，请见附加文件中的 dream.zip。