← 返回题目列表

AtCoder · ajo2025_final_c

C. 偶次网格

中文机器翻译题面 查看原题

配点 : 1200 点

問題文

L \times L 的董事会。 从上面 i 行,从左起 j 标记列中的方块 我们称之为 (i,j) 。

一开始,所有的方块都是白色的,但 Snuke 君做了以下操作。 我做了 N 次并将一些方块涂成黑色。 将

  • 操作 i (1 \leq i \leq N): 長方形領域 [A_i,B_i] \times [C_i,D_i] 漆成黑色。 更准确地说,所有正方形 (r,c) (A_i \leq r \leq B_i, C_i \leq c \leq D_i),将其颜色设置为黑色。

从现在开始,在每个白色方块中 写入 0 or 1 。 但是,书写方法必须满足以下条件。

  • 任何 2 \times 2 关于面积,其 4 如果所有方块都是白色,则写入的值的总和为偶数。

顺便说一下,Snuke 有 M 的承诺 有。 i 第二个痴迷是质量 要写入 (X_i,Y_i) 的数字是 我希望它是 V_i 。 承诺 当 i 满足时,Snuke 您将获得 2^{M-i} 的快乐。

求 Snuke 可以获得的幸福总量的最大值。 此外,答案是 M 数字 2 请输出为十进制数。

制約

  • 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 or 1
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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 数字 2 输出为基数。 可以满足


入力例 1

3 0 4
1 1 0
1 3 0
3 1 0
3 3 1

出力例 1

1110

承诺 有 1,2,3 ,但在这种情况下, 4 无法满足。


入力例 2

3 1 4
2 2 2 2
1 1 0
1 3 0
3 1 0
3 3 1

出力例 2

1111

入力例 3

8 3 20
2 2 1 6
2 2 3 5
1 2 6 6
4 3 1
5 8 0
3 5 0
1 5 1
1 8 0
2 8 1
3 3 0
3 3 1
6 7 1
6 1 0
1 7 0
5 1 0
5 2 0
4 8 0
7 3 1
3 8 1
4 1 0
6 5 0
1 8 0
8 6 0

出力例 3

11111110111011110111

入力例 4

15 5 20
5 12 5 7
2 15 6 6
7 14 12 12
8 11 11 14
6 14 7 7
15 15 1
4 10 0
6 9 0
5 2 1
5 10 1
2 10 0
6 3 1
12 3 0
11 10 1
9 3 1
5 9 0
2 2 1
9 10 0
12 2 0
5 15 1
9 8 0
9 2 0
5 3 1
6 10 0
2 9 0

出力例 4

11111111111111110100