配点 : 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