如果可以将数组分为 $$$k>1$$$ 部分,以便每个部分的值按位异或相等,那么我们称数组 $$$x_1,\dots,x_m$$$ 有趣。
更正式地说,您必须将数组 $$$x$$$ 拆分为 $$$k$$$ 连续段,$$$x$$$ 的每个元素必须恰好属于 $$$1$$$ 段。令 $$$y_1,\dots,y_k$$$ 分别为每个部分的元素的异或。那么 $$$y_1=y_2=\dots=y_k$$$ 必须满足。
例如,如果 $$$x = [1, 1, 2, 3, 0]$$$,则可以按如下方式拆分:$$$[\color{blue}1], [\color{green}1], [\color{red}2, \color{red}3, \color{red}0]$$$。确实$$$\color{blue}1=\color{green}1=\color{red}2 \oplus \color{red}3\oplus \color{red}0$$$。
给你一个数组 $$$a_1,\dots,a_n$$$。您的任务是回答 $$$q$$$ 查询:
- 对于固定的$$$l$$$, $$$r$$$,判断子数组$$$a_l,a_{l+1},\dots,a_r$$$是否有趣。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$)——分别是数组中的元素数量和查询数量。
下一行包含 $$$n$$$ 整数 $$$a_1,\dots,a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — 数组的元素。
接下来的 $$$q$$$ 行包含两个描述查询的整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,如果子数组有趣,则输出“YES”,否则输出“NO”。
在任何情况下都可以输出“Yes”和“No”(例如,字符串“yES”、“yes”和“Yes”将被识别为正确答案)。
示例
输入 #1
4 5 5 1 1 2 3 0 1 5 2 4 3 5 1 3 3 4 5 5 1 2 3 4 5 1 5 2 4 3 5 1 3 2 3 7 4 12 9 10 9 10 11 9 1 5 1 7 2 6 2 7 11 4 0 0 1 0 0 1 0 1 1 0 1 1 2 2 5 6 9 7 11
输出 #1
YES YES NO NO NO YES NO NO YES NO NO NO NO NO YES NO YES YES
注意
第一个测试用例的说明:
第一个查询在语句中进行了描述。
在第二个查询中,我们应该除$$$[1,2,3]$$$。可能的除法是$$$[1,2],[3]$$$,因为$$$1\oplus 2=3$$$。
可以看出,对于查询 $$$3,4,5$$$,子数组并不重要。