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。