小 L 和小 Q 刚刚学习了异或运算，老师为了强化他们对异或的理解，在课堂上组织了这样一个游戏。
有一个长度为 n 的非负数组 A 下标均从 1 开始。
游戏一共会进行 q 轮，在每一轮游戏中，会事先给出 4 个参数 l_1, r_1, l_2, r_2，满足 1 \le l_1 \le r_1 \le n、1 \le l_2 \le r_2 \le n。小 L 先选择一个 l_1 \sim r_1 之间的下标 x，然后小 Q 选择一个 l_2 \sim r_2 之间的下标 y。定义这一轮游戏中二人的得分是 a_x \oplus a_y（即两个数做异或运算）。
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。
第一行输入三个正整数 n, q，分别表示数组 A的长度和游戏轮数。
第二行：n 个整数，表示 a_i，分别表示数组 A 的元素。
接下来 q 行，每行四个正整数，表示这一轮游戏的 l_1, r_1, l_2, r_2。
输出共 q 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。
10 5 1651 253 1 10 151 666 206 9 15 55 1 1 1 2 1 3 1 3 1 5 9 9 1 5 2 8 4 5 1 2
0 0 1660 1257 247
对于所有数据，1 \le n, q \le 15000, 0 \leq a_i \leq 20000
样例解释：
第一轮游戏小 L 只能选择第一个数字 1651 ，小 Q 选择 1651 使得结果为 0.
第二轮游戏小 L 不论选什么，小 Q 都可以选一样的数字使得结果为0。
第三轮游戏小 L 可以选 1651 可以保证（2进制下）第11位是1 ，小 Q 只能选择15，1651 \oplus 15 =1660
第四轮游戏小 L 选择 1651 ，小 Q 选择 666，1651 \oplus 666 = 1257
第五轮游戏小 L 选择 10 ，小 Q 选 253 ，10 \oplus 253 = 247
| 时间限制 | 2 秒 |
| 内存限制 | 128 MB |