题目描述

相信大家都有吃过异或粽子 ，今天我们来吃异或月饼。

小L是一个喜欢吃月饼的孩子，今天她要来做月饼。月饼有 $n$ 种不同的馅，小L每次询问一个区间 $[l_i,r_i]$ 表明她想在这个区间内选取一段连续的馅做月饼，做成的月饼的美味度相当于这些馅美味度的异或和，她希望你帮她找出她能做出的最美味的馅饼的美味度是多少。

如果你回答出正确的答案，她会分一些异或月饼给你品尝。

输入格式

第一行两个数 $n$ 和 $q$。

接下来有 $q$ 行，一行两个数 $l_i,r_i$ ，表示当前询问的区间。

强制在线，设 $lst$ 为上一次询问的答案，此次询问输入的 $l_i,r_i$ 加上 $lst$ 后对 $n$ 取模 $+1$ 得到真正询问。

不保证 $l_i \le r_i$。

输出格式

输出一共 $q$ 行，每行一个数表示询问的结果

样例 #1

样例输入 #1

9 10
9 1 1 7 8 0 2 7 3
10 7
2 7
7 6
8 1
7 6
5 9
2 4
1 2
9 2
6 4

样例输出 #1

15
14
7
7
8
14
15
7
15
7

样例输入 #1

8 10
321517131 344439215 253845141 22596671 1071053927 112508707 152573495 307288519
3 0
5 1
6 6
7 7
2 8
1 5
3 4
8 6
8 3
4 7

样例输出 #2

463923002
1071053927
112508707
253845141
503083219
1071053927
253845141
1071053927
1071053927
1071053927

数据范围

对于 $20\%$ 的数据，保证 $n,q \le 200$。

对于 $50\%$ 的数据，保证 $n,q \le 2000$。

对于 $100\%$ 的数据，保证 $n \le 12000$，$q \le 6000$，其余输入在 $\text{int}$ 范围内。