AT_ajo2025_final_c Even Subgrid

有一个 $L \times L$ 的棋盘。我们将从上往下的第 $i$ 行、从左往右的第 $j$ 列的格子记作格子 $(i, j)$。 最开始所有格子都是白色的，不过“SUNUKE 君”进行了 $N$ 次如下操作，使得部分格子变成了黑色： - 第 $i$ 次操作（$1 \leq i \leq N$）：将矩形区域 $[A_i, B_i] \times [C_i, D_i]$ 的格子全部涂成黑色。更精确地说，就是把所有满足 $A_i \leq r \leq B_i$ 且 $C_i \leq c \leq D_i$ 的格子 $(r,c)$ 都变为黑色。 接下来，要求你在每个白色格子上写下 $0$ 或 $1$。但写法需要满足如下条件： - 对于任意的 $2 \times 2$ 区域，如果其中 $4$ 个格子全是白色，那么它们对应写下的数之和必须为偶数。 除此之外，SUNUKE 君还有 $M$ 个“执念”。第 $i$ 个执念要求格子 $(X_i, Y_i)$ 上写下的数必须是 $V_i$。如果执念 $i$ 被满足，SUNUKE 君就可以获得 $2^{M-i}$ 的快乐值。 请计算 SUNUKE 君可以获得的最大快乐值之和。最终答案请以 $M$ 位二进制数的形式输出。

输入按以下格式从标准输入读入： > $L$ $N$ $M$ > $A_1$ $B_1$ $C_1$ $D_1$ > $A_2$ $B_2$ $C_2$ $D_2$ > $\vdots$ > $A_N$ $B_N$ $C_N$ $D_N$ > $X_1$ $Y_1$ $V_1$ > $X_2$ $Y_2$ $V_2$ > $\vdots$ > $X_M$ $Y_M$ $V_M$

请以 $M$ 位二进制数输出答案。

### 样例解释 1 可以满足执念 $1,2,3$，但那样的话执念 $4$ 就无法满足。 ### 数据范围 - $1 \leq L \leq 10^9$ - $0 \leq N \leq 250$ - $1 \leq M \leq 10^5$ - $1 \leq A_i \leq B_i \leq L$ - $1 \leq C_i \leq D_i \leq L$ - $1 \leq X_i, Y_i \leq L$ - 保证格子 $(X_i,Y_i)$ 都是白色 - $V_i = 0$ 或 $1$ - 所有输入均为整数。 由 ChatGPT 5 翻译