Sofa Thief
Contest: Educational Codeforces Round 24
Difficulty rating: 2000
Tags: brute force, implementation

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 xa < xb, 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 ya < yb, 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 cntl sofas to the left of Grandpa Maks's sofa, cntr — to the right, cntt — to the top and cntb — 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 format:
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 x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m) — coordinates of the i-th sofa. It is guaranteed that cells (x1, y1) and (x2, y2) have common side, (x1, y1)  ≠  (x2, y2) and no cell is covered by more than one sofa.

The last line contains four integer numbers cntl, cntr, cntt, cntb (0 ≤ cntl, cntr, cntt, cntb ≤ d - 1).

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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 cntl = 2, cntr = 1, cntt = 2 and cntb = 0.
- The third sofa has cntl = 2, cntr = 1, cntt = 1 and cntb = 1.

So the second one corresponds to the given conditions.

In the third example

- The first sofa has cntl = 1, cntr = 1, cntt = 0 and cntb = 1.
- The second sofa has cntl = 1, cntr = 1, cntt = 1 and cntb = 0.

And there is no sofa with the set (1, 0, 0, 0) so the answer is -1.

Example input:
2
3 2
3 1 3 2
1 2 2 2
1 0 0 1

Example output:
1

Example input:
3
10 10
1 2 1 1
5 5 6 5
6 4 5 4
2 1 2 0

Example output:
2

Editorial:
Coordinates don't exceed 105 so it's possible to use sweep line method to solve the problem.
Let's calculate cnt value separately for each side. I will show the algorithm for left side and all the others will be done similarly.
Let cnt_left[i] be the number of sofas which has smaller of their x coordinates less than or equal to i. To count that let's firstly increment by one cnt_left[min(x1i, x2i)] for all sofas and then proceed from left to right and do cnt_left[i] = cnt_left[i] + cnt_left[i - 1].
Now cnt_left[max(x1i, x2i) - 1] will represent number of sofas to the left of the current one but the sofa itself can also be counted. You need to decrement the result by one if x1i ≠ x2i.
The same is for top value but with y coordinates insted of x.
For the right and bottom values you should calculate cnt_right[max(x1i, x2i)] and cnt_bottom[max(y1i, y2i)]. Then take cnt_right[min(x1i, x2i) + 1] and cnt_bottom[min(y1i, y2i) + 1].
The only thing left is to compare values of each sofa with given ones and find the suitable sofa.
Overall complexity: O(n).