当前没有测试数据。

题目描述

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

定义组合数$\binom ij=\begin{cases}\frac{i!}{j!(i-j)!}&i\geq j\geq0\\0&\text{其余情况}\end{cases}$,可以证明对于任意$i,j,\binom ij$总是整数。

这天，骐度空间·莫羯座·十一月的萧彰遇到了一道难题。有一个 n × n 的矩阵，(i, j) 表示第 i 行第 j

列，有 Q 次操作，每次操作给定子矩阵的两个端点（分别为 (x1, y1) 和 (x2, y2)），对于所有原矩

阵中所有位置 (x, y) 满足 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2 加上 (^x_y−</sub>⁻_y^x₁¹)。

骐度空间·莫羯座·十一月的萧彰凭借超强的能力在 0.0001s 内算出了答案，但他想考考你，顺便帮忙

验证一下。

骐度空间·莫羯座·十一月的萧彰想知道最后的矩阵长什么样，由于数很大，为了方便，每个位置的值都 要对 10⁹ + 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

最终的矩阵如下：

1 0 1
1 1 1
1 2 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

最终的矩阵如下：

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 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

数据范围限制

对于 10% 的数据，满足 1 ≤ n, Q ≤ 10。

对于 30% 的数据，满足 1 ≤ n, Q ≤ 100。

对于 40% 的数据，满足 1 ≤ n, Q ≤ 500。

对于另外 20% 的数据，满足所有操作的 x2, y2 均等于 n。

对于 100% 的数据，满足 1 ≤ n, Q ≤ 5000。

对于所有数据 1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n。