Sofa Thief

题意翻译

给定沙发数量 $d$，和一个长宽分别为 $n,m$ 的长方形场地，每个沙发占两格。接下来 $d$ 行给出 $x1,y1,x2,y2$，表示每个沙发的所在位置。最后给定$cnt_l,cnt_r,cnt_t,cnt_b$，让你求出一个沙发使得在它左边的沙发有 $cnt_l$ 个，在它右边的沙发有 $cnt_r$ 个，在它上面的沙发有 $cnt_t$ 个，在它下面的沙发有 $cnt_b$ 个。如果没有满足条件的沙发，输出 $-1$。 一个沙发 $a$ 在另一个沙发 $b$ 左边是指沙发 $a$ 的某一个 $x_i$ 与沙发 $b$ 的某一个 $x_j$ 满足 $x_i<x_j$。 同样的，一个沙发 $a$ 在另一个沙发 $b$ 右边是指沙发 $a$ 的某一个 $x_i$ 与沙发 $b$ 的某一个 $x_j$ 满足 $x_i>x_j$。 一个沙发 $a$ 在另一个沙发 $b$ 上面是指沙发 $a$ 的某一个 $y_i$ 与沙发 $b$ 的某一个 $y_j$ 满足 $y_i<y_j$。 同样的，一个沙发 $a$ 在另一个沙发 $b$ 下面是指沙发 $a$ 的某一个 $y_i$ 与沙发 $b$ 的某一个 $y_j$ 满足 $y_i>y_j$。 因此，我们需要注意，一个沙发 $a$ 可能既在另一个沙发 $b$ 的左边又在它的右边。 同样的，一个沙发 $a$ 也可能既在另一个沙发 $b$ 的上面又在它的下面。

题目描述

Yet another round on DecoForces is coming! Grandpa Maks wanted to participate in it but someone has stolen his precious sofa! And how can one perform well with such a major loss? Fortunately, the thief had left a note for Grandpa Maks. This note got Maks to the sofa storehouse. Still he had no idea which sofa belongs to him as they all looked the same! The storehouse is represented as matrix $ n×m $ . Every sofa takes two neighbouring by some side cells. No cell is covered by more than one sofa. There can be empty cells. Sofa $ A $ is standing to the left of sofa $ B $ if there exist two such cells $ a $ and $ b $ that $ x_{a}&lt;x_{b} $ , $ a $ is covered by $ A $ and $ b $ is covered by $ B $ . Sofa $ A $ is standing to the top of sofa $ B $ if there exist two such cells $ a $ and $ b $ that $ y_{a}&lt;y_{b} $ , $ a $ is covered by $ A $ and $ b $ is covered by $ B $ . Right and bottom conditions are declared the same way. Note that in all conditions $ A≠B $ . Also some sofa $ A $ can be both to the top of another sofa $ B $ and to the bottom of it. The same is for left and right conditions. The note also stated that there are $ cnt_{l} $ sofas to the left of Grandpa Maks's sofa, $ cnt_{r} $ — to the right, $ cnt_{t} $ — to the top and $ cnt_{b} $ — to the bottom. Grandpa Maks asks you to help him to identify his sofa. It is guaranteed that there is no more than one sofa of given conditions. Output the number of Grandpa Maks's sofa. If there is no such sofa that all the conditions are met for it then output -1.

输入输出格式

输入格式

The first line contains one integer number $ d $ ( $ 1<=d<=10^{5} $ ) — the number of sofas in the storehouse. The second line contains two integer numbers $ n $ , $ m $ ( $ 1<=n,m<=10^{5} $ ) — the size of the storehouse. Next $ d $ lines contains four integer numbers $ x_{1} $ , $ y_{1} $ , $ x_{2} $ , $ y_{2} $ ( $ 1<=x_{1},x_{2}<=n $ , $ 1<=y_{1},y_{2}<=m $ ) — coordinates of the $ i $ -th sofa. It is guaranteed that cells ( $ x_{1},y_{1} $ ) and ( $ x_{2},y_{2} $ ) have common side, ( $ x_{1},y_{1} $ ) $ ≠ $ ( $ x_{2},y_{2} $ ) and no cell is covered by more than one sofa. The last line contains four integer numbers $ cnt_{l} $ , $ cnt_{r} $ , $ cnt_{t} $ , $ cnt_{b} $ ( $ 0<=cnt_{l},cnt_{r},cnt_{t},cnt_{b}<=d-1 $ ).

输出格式

Print the number of the sofa for which all the conditions are met. Sofas are numbered $ 1 $ through $ d $ as given in input. If there is no such sofa then print -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

说明

Let's consider the second example. - The first sofa has $ 0 $ to its left, $ 2 $ sofas to its right ( $ (1,1) $ is to the left of both $ (5,5) $ and $ (5,4) $ ), $ 0 $ to its top and $ 2 $ to its bottom (both $ 2 $ nd and $ 3 $ rd sofas are below). - The second sofa has $ cnt_{l}=2 $ , $ cnt_{r}=1 $ , $ cnt_{t}=2 $ and $ cnt_{b}=0 $ . - The third sofa has $ cnt_{l}=2 $ , $ cnt_{r}=1 $ , $ cnt_{t}=1 $ and $ cnt_{b}=1 $ . So the second one corresponds to the given conditions. In the third example - The first sofa has $ cnt_{l}=1 $ , $ cnt_{r}=1 $ , $ cnt_{t}=0 $ and $ cnt_{b}=1 $ . - The second sofa has $ cnt_{l}=1 $ , $ cnt_{r}=1 $ , $ cnt_{t}=1 $ and $ cnt_{b}=0 $ . And there is no sofa with the set $ (1,0,0,0) $ so the answer is -1.

题意翻译

给定沙发数量 $d$，和一个长宽分别为 $n,m$ 的长方形场地，每个沙发占两格。接下来 $d$ 行给出 $x1,y1,x2,y2$，表示每个沙发的所在位置。最后给定$cnt_l,cnt_r,cnt_t,cnt_b$，让你求出一个沙发使得在它左边的沙发有 $cnt_l$ 个，在它右边的沙发有 $cnt_r$ 个，在它上面的沙发有 $cnt_t$ 个，在它下面的沙发有 $cnt_b$ 个。如果没有满足条件的沙发，输出 $-1$。 一个沙发 $a$ 在另一个沙发 $b$ 左边是指沙发 $a$ 的某一个 $x_i$ 与沙发 $b$ 的某一个 $x_j$ 满足 $x_i<x_j$。 同样的，一个沙发 $a$ 在另一个沙发 $b$ 右边是指沙发 $a$ 的某一个 $x_i$ 与沙发 $b$ 的某一个 $x_j$ 满足 $x_i>x_j$。 一个沙发 $a$ 在另一个沙发 $b$ 上面是指沙发 $a$ 的某一个 $y_i$ 与沙发 $b$ 的某一个 $y_j$ 满足 $y_i<y_j$。 同样的，一个沙发 $a$ 在另一个沙发 $b$ 下面是指沙发 $a$ 的某一个 $y_i$ 与沙发 $b$ 的某一个 $y_j$ 满足 $y_i>y_j$。 因此，我们需要注意，一个沙发 $a$ 可能既在另一个沙发 $b$ 的左边又在它的右边。 同样的，一个沙发 $a$ 也可能既在另一个沙发 $b$ 的上面又在它的下面。