English · Original
Chinese · Translation
Formal · Original
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_ < _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_ < _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_.
## Input
The first line contains one integer number _d_ (1 ≤ _d_ ≤ 105) — the number of sofas in the storehouse.
The second line contains two integer numbers _n_, _m_ (1 ≤ _n_, _m_ ≤ 105) — 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).
## Output
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_.
[samples]
## Note
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 2nd and 3rd 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_.
又一场 DecoForces 的比赛即将来临！爷爷 Maks 想参加这场比赛，但有人偷走了他心爱的沙发！没有沙发，一个人怎么能表现得好呢？
幸运的是，小偷给爷爷 Maks 留了一张纸条。这张纸条引导 Maks 来到了沙发仓库。但他仍然不知道哪个沙发是他的，因为它们看起来都一样！
仓库用一个 #cf_span[n × m] 的矩阵表示。每个沙发占据两个由某条边相邻的格子。每个格子最多被一个沙发覆盖。可能存在空格子。
沙发 #cf_span[A] 在沙发 #cf_span[B] 的左侧，当且仅当存在两个格子 #cf_span[a] 和 #cf_span[b]，使得 *#cf_span[xa < xb]*，#cf_span[a] 被 #cf_span[A] 覆盖，#cf_span[b] 被 #cf_span[B] 覆盖。沙发 #cf_span[A] 在沙发 #cf_span[B] 的上方，当且仅当存在两个格子 #cf_span[a] 和 #cf_span[b]，使得 *#cf_span[ya < yb]*，#cf_span[a] 被 #cf_span[A] 覆盖，#cf_span[b] 被 #cf_span[B] 覆盖。右侧和下方的条件同理定义。
*注意：所有条件中 #cf_span[A ≠ B]。* 此外，某个沙发 #cf_span[A] 可以同时在另一个沙发 #cf_span[B] 的上方和下方。左右关系同理。
纸条还指出，有 #cf_span[cntl] 个沙发在爷爷 Maks 的沙发左侧，#cf_span[cntr] 个在右侧，#cf_span[cntt] 个在上方，#cf_span[cntb] 个在下方。
爷爷 Maks 请你帮他找出他的沙发。保证至多只有一个沙发满足这些条件。
请输出爷爷 Maks 的沙发编号。如果没有沙发满足所有条件，则输出 _-1_。
第一行包含一个整数 #cf_span[d] (#cf_span[1 ≤ d ≤ 105]) —— 仓库中沙发的数量。
第二行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 105]) —— 仓库的尺寸。
接下来 #cf_span[d] 行，每行包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[1 ≤ x1, x2 ≤ n], #cf_span[1 ≤ y1, y2 ≤ m]) —— 第 #cf_span[i] 个沙发的坐标。保证格子 (#cf_span[x1, y1]) 和 (#cf_span[x2, y2]) 共享一条边，(#cf_span[x1, y1]) #cf_span[ ≠ ] (#cf_span[x2, y2])，且没有格子被多个沙发覆盖。
最后一行包含四个整数 #cf_span[cntl], #cf_span[cntr], #cf_span[cntt], #cf_span[cntb] (#cf_span[0 ≤ cntl, cntr, cntt, cntb ≤ d - 1])。
输出满足所有条件的沙发编号。沙发按输入顺序编号为 #cf_span[1] 到 #cf_span[d]。如果没有这样的沙发，则输出 _-1_。
考虑第二个示例：
第二个沙发符合给定条件。
在第三个示例中：
不存在满足集合 #cf_span[(1, 0, 0, 0)] 的沙发，因此答案为 _-1_。
## Input
第一行包含一个整数 #cf_span[d] (#cf_span[1 ≤ d ≤ 105]) —— 仓库中沙发的数量。第二行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n, m ≤ 105]) —— 仓库的尺寸。接下来 #cf_span[d] 行，每行包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[1 ≤ x1, x2 ≤ n], #cf_span[1 ≤ y1, y2 ≤ m]) —— 第 #cf_span[i] 个沙发的坐标。保证格子 (#cf_span[x1, y1]) 和 (#cf_span[x2, y2]) 共享一条边，(#cf_span[x1, y1]) #cf_span[ ≠ ] (#cf_span[x2, y2])，且没有格子被多个沙发覆盖。最后一行包含四个整数 #cf_span[cntl], #cf_span[cntr], #cf_span[cntt], #cf_span[cntb] (#cf_span[0 ≤ cntl, cntr, cntt, cntb ≤ d - 1])。
## Output
输出满足所有条件的沙发编号。沙发按输入顺序编号为 #cf_span[1] 到 #cf_span[d]。如果没有这样的沙发，则输出 _-1_。
[samples]
## Note
考虑第二个示例：
第一个沙发左侧有 #cf_span[0] 个沙发，右侧有 #cf_span[2] 个沙发（格子 #cf_span[(1, 1)] 在 #cf_span[(5, 5)] 和 #cf_span[(5, 4)] 的左侧），上方有 #cf_span[0] 个沙发，下方有 #cf_span[2] 个沙发（第二和第三个沙发都在其下方）。
第二个沙发有 #cf_span[cntl = 2]，#cf_span[cntr = 1]，#cf_span[cntt = 2]，#cf_span[cntb = 0]。
第三个沙发有 #cf_span[cntl = 2]，#cf_span[cntr = 1]，#cf_span[cntt = 1]，#cf_span[cntb = 1]。
因此第二个沙发符合给定条件。
在第三个示例中：
第一个沙发有 #cf_span[cntl = 1]，#cf_span[cntr = 1]，#cf_span[cntt = 0]，#cf_span[cntb = 1]。
第二个沙发有 #cf_span[cntl = 1]，#cf_span[cntr = 1]，#cf_span[cntt = 1]，#cf_span[cntb = 0]。
不存在满足集合 #cf_span[(1, 0, 0, 0)] 的沙发，因此答案为 _-1_。
**Definitions**
Let $ d \in \mathbb{Z}^+ $ be the number of sofas.
Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the grid.
For each sofa $ i \in \{1, \dots, d\} $, let $ S_i = \{(x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2})\} $ be the set of two adjacent grid cells it occupies, with $ (x_{i,1}, y_{i,1}) \neq (x_{i,2}, y_{i,2}) $ and $ |x_{i,1} - x_{i,2}| + |y_{i,1} - y_{i,2}| = 1 $.
Let $ C = (cntl, cntr, cntt, cntb) \in \mathbb{Z}_{\geq 0}^4 $ be the given counts of sofas to the left, right, top, and bottom of Grandpa Maks’s sofa.
**Constraints**
1. $ 1 \leq d \leq 10^5 $
2. $ 1 \leq n, m \leq 10^5 $
3. All sofa cells are distinct and lie within $ [1, n] \times [1, m] $.
4. $ 0 \leq cntl, cntr, cntt, cntb \leq d - 1 $
**Objective**
For each sofa $ i \in \{1, \dots, d\} $, define:
- $ L_i = \#\{ j \neq i \mid \exists (x_j, y_j) \in S_j, \exists (x_i, y_i) \in S_i \text{ such that } x_j < x_i \} $
- $ R_i = \#\{ j \neq i \mid \exists (x_j, y_j) \in S_j, \exists (x_i, y_i) \in S_i \text{ such that } x_j > x_i \} $
- $ T_i = \#\{ j \neq i \mid \exists (x_j, y_j) \in S_j, \exists (x_i, y_i) \in S_i \text{ such that } y_j < y_i \} $
- $ B_i = \#\{ j \neq i \mid \exists (x_j, y_j) \in S_j, \exists (x_i, y_i) \in S_i \text{ such that } y_j > y_i \} $
Find the unique $ i \in \{1, \dots, d\} $ such that:
$$
L_i = cntl, \quad R_i = cntr, \quad T_i = cntt, \quad B_i = cntb
$$
If no such $ i $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "C. Sofa Thief",
"description": {
"content": "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 thi",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF818C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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?\n\nFortunately, the thi...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "又一场 DecoForces 的比赛即将来临！爷爷 Maks 想参加这场比赛，但有人偷走了他心爱的沙发！没有沙发，一个人怎么能表现得好呢？\n\n幸运的是，小偷给爷爷 Maks 留了一张纸条。这张纸条引导 Maks 来到了沙发仓库。但他仍然不知道哪个沙发是他的，因为它们看起来都一样！\n\n仓库用一个 #cf_span[n × m] 的矩阵表示。每个沙发占据两个由某条边相邻的格子。每个格子最多被一个沙发覆...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ d \\in \\mathbb{Z}^+ $ be the number of sofas. \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the grid. \nFor each sofa $ i \\in \\{1, \\dots, d\\} $, let $ S_i = \\{(x_{i,1}, y...",
"is_translate": false,
"language": "Formal"
}
]
}