题目描述

CC 最近学习了数组的相关内容，构造出了一个很奇怪的数组，然后提出了一些问题。可是由于 CC 实在是太菜了，根本切不动这道题，因此，需要你来帮他。

这是一个 $(n + 1) \times (n + 1)$ 的数组，有 $q$ 次询问，每次给定四个数，求这个子矩阵的异或和。

数组的构造方法如下：

• 行和列编号从 $0 \sim n$ 。
• 对于所有 $0 \leq i \leq n$，有 $a_{i,\, 0}=a_{0,\, i}=1$ 。
• 对于所有 $1 \leq i, j \leq n$ 有，$a_{i,\, j} = a_{i - 1,\, j} \oplus a_{i,\, j- 1}$ 。

输入格式

输入第一行两个数，$n$ 和 $q$ ，含义与上述题面相同。

接下来 $q$ 行，给定四个整数 $x_1,\,y_1,\,x_2,\,y_2$ ，表示询问 $(x_1,\, y_1) \sim (x_2,\, y_2)$ 这个子矩阵的异或和。

输出格式

输出 $q$ 行，每行一个整数，表示询问的答案。

样例

6 6
4 1 6 4
1 1 6 1
4 3 5 4
6 5 6 5
4 3 6 3
5 1 6 4

1
1
1
0
1
0

提示

温馨提醒

题目输入量较大，请自行使用较快的输入输出方式。

样例解释

构造出来的数组如下：

1 1 1 1 1 1 1
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 0 0 0 1 0 0
1 1 1 1 0 0 0
1 0 1 0 0 0 0
1 1 0 0 0 0 0

数据范围

对于 $20 \,\%$ 的数据 $1 \leq n,\, q \leq 100$ 。

对于 $60\, \%$ 的数据 $1 \leq n,\, q \leq 2 \times 10^3$ 。

对于 $100 \, \%$ 的数据 $1 \leq n \leq 10^{18}$，$1 \leq q \leq 5 \times 10^5$ 且 $1 \leq x_1,\,y_1,\,x_2,\,y_2 \leq n$ 。