[R28F]矩形异或 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个 $n \times m$ 的矩阵 $A$，其中每个元素初始为非负整数。

同时给定 $k$ 个矩形区域，每个区域由左上角坐标 $(x_{i_1}, y_{i_1})$ 和右下角坐标 $(x_{i_2}, y_{i_2})$ 描述。

对于每个矩形，你可以选择一个非负整数 $v_i$，并将该矩形区域内的所有元素都异或上 $v_i$。注意：每个矩形只能操作一次。

求是否存在一组非负整数 $v_1, v_2, \dots, v_k$，使得经过所有操作后，矩阵中每个元素都变为 $0$？若存在，输出 Yes 并给出一组可行的 $v_i$；否则输出 No。

格式

输入格式

第一行包含三个整数 $n, m, k$，分别表示矩阵的行数、列数和特殊矩形的数量。

接下来 $n$ 行，每行包含 $m$ 个整数，描述初始矩阵 $A$。

接下来 $k$ 行，每行包含四个整数 $x_{i_1}, y_{i_1}, x_{i_2}, y_{i_2}$，描述第 $i$ 个特殊矩形区域。矩阵的行和列都从 $1$ 开始编号。

输出格式

如果存在可行的方案：第一行输出 Yes。

第二行输出 $k$ 个整数，用空格隔开，分别表示对第 $1, 2, \dots, k$ 个矩形操作的值 $v_1, v_2, \dots, v_k$（要求 $0 \leq v_i < 2^{30}$)。

如果不存在可行的方案，只输出一行 No。

样例

样例输入 #1

3 3 1
0 0 0
0 5 5
0 5 5
2 2 3 3

样例输出 #1

Yes
5

样例输入 #2

2 2 3
3 3
3 3
1 1 1 2
1 2 2 2
1 1 2 1

样例输出 #2

Yes
0 3 3

数据规模

对于 $30\%$ 的数据，$k \leq 10$，$1 \leq n \times m \leq 500$。

对于 $100\%$ 的数据，$1 \leq n \times m \leq 3000$，$1 \leq k \leq 1000$，$0 \leq A_{i,j} < 2^{30}$， $1 \leq x_{i_1} \leq x_{i_2} \leq n, 1 \leq y_{i_1} \leq y_{i_2} \leq m$。