配点 : 700 点
問題文
N 卡,并且按顺序
称之为第 1, 2, \cdots ,N 张牌。所有卡片都有正面和背面 0 和
按字典顺序比较 1 。
这些卡 M 将其正面或背面朝上放在桌子上,以满足所有条件。 第i 条件是满足以下至少一项。 卡顶部的
- A_i 。 X_i 。
- B_i 。 Y_i 。
保证仅给出存在的输入,从而存在满足条件的放置卡的方式。然而,放置卡片的方式可能有多种。满足以下条件的一组整数 查找 (p, q, r, s) 的编号。
- 1 \leq p, q \leq N
- \{r, s\} \subset \{0, 1\}
- 关于所有牌的放置,至少满足以下条件之一。
- p 。 r 。
- q 。 s 。
制約
- 1 \leq N \leq 3 \times 10^4
- 0 \leq M \leq 3 \times 10^4
- 1 \leq A_i, B_i \leq N
- \{ X_i, Y_i \} \subset \{0, 1\}
- 放置符合条件的卡牌的最佳方式是 1 存在。
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M A_1 B_1 X_1 Y_1 A_2 B_2 X_2 Y_2 \vdots A_M B_M X_M Y_M
出力
将答案输出在一行。
入力例 1
2 1 1 2 0 0
出力例 1
6
1 第张卡和 2 位于任何卡片的顶部。 必须写 0 。如果您放置卡片使其满足此要求,则卡片正面可能写的字符为 (0, 0), (1, 0), (0, 1) 可以得到第 3 没错。因此, (p, q, r, s) 可能是: 有 (1, 1, 0, 1), (1, 1, 1, 0), (1, 2, 0, 0), (2, 1, 0, 0), (2, 2, 0, 1), (2, 2, 1, 0) 。
入力例 2
10 20 4 10 1 1 7 3 0 1 6 4 1 1 8 1 1 1 7 5 0 0 2 8 0 0 1 6 1 1 2 2 1 0 4 8 0 0 3 3 1 1 9 6 0 1 9 2 0 1 5 2 1 0 5 7 1 1 2 2 1 1 5 6 1 0 2 10 1 1 5 2 1 1 7 7 1 0 10 5 1 0
出力例 2
241