题目描述

众所周知，骐度空间·莫羯座·十一月的萧彰同学擅长计算，尤其擅长计算组合数。

定义组合数 $\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$ 取模。

然而输出量很大，骐度空间·莫羯座·十一月的萧彰无法快速比较这是否是正确答案，所以你只需要输出每一行的异或和和每一列的异或和即可。

骐度空间·莫羯座·十一月的萧彰担心你不知道什么是异或运算，所以他直接给你的输出答案的模板：

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);
    }
}

输入格式

第一行两个正整数 $n$，$Q$。

接下来 $Q$ 行，每行四个正整数 $x1, y1, x2, y2$，表示每次操作的子矩阵的两个端点。

输出格式

第一行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 行的异或和。

第二行 $n$ 个数，第 $i$ 个数表示最终矩阵第 $i$ 列的异或和。

3 2
1 1 3 2
1 3 3 3

0 1 2
1 3 1

5 3
1 1 3 3
2 2 5 4
1 2 5 5

0 3 0 2 8
1 6 7 12 5

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

2 0 1 10 5 1 66 9 238 246
0 0 44 84 3 81 66 40 0 30

提示

样例解释 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$。