给定一个长度为  的非负整数序列 。

现有  次查询，每次查询给定一个区间 。对于每次查询，你需要从区间  所包含的元素构成的多重集  中挑选一个大小最大的子集 ，使得  中任意两个元素的权值互不相同。随后，你可以从选出的集合  中再任选一个子集 （允许为空集）。设  为集合  的大小， 为集合  中所有元素权值的按位异或和（空集的异或和规定为 ），求出  的最小值。

本题强制在线。每次查询给出的  是加密后的结果。记上一次查询的答案为 （初始时 ）。实际的查询区间端点  可通过如下方式解密得到：

                                                                                                           

                                                                                                          

解密后，若 ，你需要交换  和  的值。

输入描述:

第一行包含两个整数  ()。

第二行包含  个整数  ()。

接下来  行，每行两个整数  ()，表示加密后的查询区间端点。

输出描述:

对于每组询问，输出一行一个数字表示结果。

6 3
4 4 6 6 0 0
6 6
2 4
6 3

1
2
1

备注:

初始 lastans = 0。
第一次查询：解密得 l = 1, r = 1。区间内元素构成的集合 S = 4，|S| = 1。选空集 ∅（异或和为 0），答案为 1 ⊕ 0 = 1。更新 lastans = 1。
第二次查询：解密得 l = 4, r = 6。区间内元素构成的集合 S = 0, 6，|S| = 2。选空集 ∅（异或和为 0），答案为 2 ⊕ 0 = 2。更新 lastans = 2。
第三次查询：解密得 l = 5, r = 2，交换端点得 [2, 5]。区间内元素构成的集合 S = 0, 4, 6，|S| = 3。选子集 4, 6（异或和为 2），答案为 3 ⊕ 2 = 1。更新 lastans = 1。
本题输入输出数据量较大，建议使用较快的输入输出方式。C++ 选手建议使用 scanf/printf，或在使用 cin/cout 时取消同步流：
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);