← 返回题目列表

Codeforces · 818/C

C. 沙发贼

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

DecoForces 的又一轮即将到来!麦克斯爷爷想参加,但他珍贵的沙发被人偷了!遭受如此重大损失,如何能够表现出色?

幸运的是,小偷给麦克斯爷爷留下了一张纸条。这张便条让马克斯来到了沙发仓库。但他仍然不知道哪张沙发是他的,因为它们看起来都一样!

仓库表示为矩阵 n × m。每个沙发都需要两个相邻的侧面单元。没有一个牢房被超过一张沙发所覆盖。可以有空单元格。

如果存在两个这样的单元格 a 和 b,xa < xb,a 被 A 覆盖,b 被 B 覆盖,则沙发 A 站在沙发 B 的左侧。如果存在两个这样的单元格 a 和 b,ya < yb,a 被 A 覆盖,b 被 B 覆盖,则沙发 A 站在沙发 B 的顶部。右侧和底部条件的声明方式相同。

请注意,在所有情况下 A ≠ B。此外,某些沙发 A 既可以位于另一个沙发 B 的顶部,也可以位于其底部。对于左侧和右侧的条件也是如此。

该注释还指出,Macs 爷爷的沙发左侧有 cntl 沙发,右侧有 cntr,顶部有 cntt,底部有 cntb。

麦克斯爷爷请你帮助他识别他的沙发。保证给定条件的沙发不超过一张。

输出麦克斯爷爷的沙发数量。如果不存在满足所有条件的沙发,则输出-1。

输入

第一行包含一个整数 d (1 ≤ d ≤ 105) — 仓库中沙发的数量。

第二行包含两个整数n, m (1 ≤ n, m ≤ 105) — 仓库的大小。

接下来的 d 行包含四个整数 x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m) — 第 i 个沙发的坐标。保证单元格 (x1, y1) 和 (x2, y2) 具有公共边,(x1, y1) ≠ (x2, y2) 并且没有单元格被多个沙发覆盖。

最后一行包含四个整数 cntl、cntr、cntt、cntb (0 ≤ cntl、cntr、cntt、cntb ≤ d - 1)。

输出

打印满足所有条件的沙发编号。根据输入中的信息,沙发的编号为 1 到 d。如果没有这样的沙发则打印-1。

示例

输入 #1

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

输出 #1

1

输入 #2

3
10 10
1 2 1 1
5 5 6 5
6 4 5 4
2 1 2 0

输出 #2

2

输入 #3

2
2 2
2 1 1 1
1 2 2 2
1 0 0 0

输出 #3

-1

注意

让我们考虑第二个例子。

- 第一个沙发的左侧有 0 个沙发,右侧有 2 个沙发((1, 1) 位于 (5, 5) 和 (5, 4) 的左侧),顶部有 0 个沙发,底部有 2 个沙发(第二个和第三个沙发都在下面)。
- 第二个沙发有 cntl = 2、cntr = 1、cntt = 2 和 cntb = 0。
- 第三张沙发有 cntl = 2、cntr = 1、cntt = 1 和 cntb = 1。

所以第二个对应于给定的条件。

在第三个例子中

- 第一个沙发有 cntl = 1、cntr = 1、cntt = 0 和 cntb = 1。
- 第二个沙发有 cntl = 1、cntr = 1、cntt = 1 和 cntb = 0。

并且不存在具有 (1, 0, 0, 0) 集合的沙发,因此答案为 -1。