众所周知，骐度空间·莫羯座·十一月的萧彰同学擅长计算，尤其擅长计算组合数。
定义组合数 $\binom{i}{j}=\begin{cases}\frac{i!}{j!(i-j)!}&i\ge j\ge 0\\0&其他情况\end{cases}$，可以证明对于任意 $i,j$，$\binom{i}{j}$ 总是整数。
这天，骐度空间·莫羯座·十一月的萧彰遇到了一道难题。有一个 $n\times n$ 的矩阵，$(i,j)$ 表示第 $i$ 行第 $j$ 列，有 $Q$ 次操作，每次操作给定子矩阵的两个端点（分别为 $(x1,y1)$ 和 $(x2,y2)$），对于所有原矩阵中的所有位置 $(x,y)$ 满足 $x1\le x\le x2$，$y1\le y\le y2$ 加上 $\binom{x-x1}{y-y1}$。
骐度空间·莫羯座·十一月的萧彰凭借超强的能力在 $0.0001s$ 内算出了答案，但他想考考你，顺便帮忙验证一下。
骐度空间·莫羯座·十一月的萧彰想知道最后的矩阵长什么样，由于数很大，为了方便，每个位置的值都要对 $10^9 + 7$ 取模。
然而输出量很大，骐度空间·莫羯座·十一月的萧彰无法快速比较这是否是正确答案，所以你只需要输出每一行的异或和和每一列的异或和即可。
骐度空间·莫羯座·十一月的萧彰担心你不知道什么是异或运算，所以他直接给你的输出答案的模板：
```cpp
int ans[5010][5010];//假设这是最终的答案矩阵
void print(){
for(int i=1;i<=n;i++){
int s=0;
for(int j=1;j<=n;j++) s^=ans[i][j];
printf("%d ",s);
}
printf("\n");
for(int i=1;i<=n;i++){
int s=0;
for(int j=1;j<=n;j++) s^=ans[j][i];
printf("%d ",s);
}
}
```
## Input
第一行两个正整数 $n$，$Q$。
接下来 $Q$ 行，每行四个正整数 $x1, y1, x2, y2$，表示每次操作的子矩阵的两个端点。
## Output
第一行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 行的异或和。
第二行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 列的异或和。
[samples]
## Note
### 样例解释 1
最终的矩阵如下：
```
1 0 1
1 1 1
1 2 1
```
### 样例解释 2
最终的矩阵如下：
```
1 1 0 0 0
1 3 1 0 0
1 4 4 1 0
0 2 5 4 1
0 2 7 9 4
```
### 数据范围
对于 $10\%$ 的数据，满足 $1 \le n, Q \le 10$。
对于 $30\%$ 的数据，满足 $1 \le n, Q \le 100$。
对于 $40\%$ 的数据，满足 $1 \le n, Q \le 500$。
对于另外 $20\%$ 的数据，满足所有操作的 $x2, y2$ 均等于 $n$。
对于 $100\%$ 的数据，满足 $1 \le n, Q \le 5000$。
对于所有数据 $1 \le x1 \le x2 \le n, 1 \le y1 \le y2 \le n$。