Description

To prepare a unique awards ceremony, the organizers lay several rectangular carpets on a rectangular area of the venue (regarded as the first quadrant of the plane Cartesian coordinate system). There are $n$ carpets, numbered from $1$ to $n$. These carpets are laid, in increasing order of their indices, axis-parallel; a later carpet is placed on top of those already laid.

After all carpets have been laid, the organizers want to know the index of the topmost carpet that covers a given point on the floor. Note: points on the boundary and at the four vertices of a rectangular carpet are also considered covered.

Input Format

The input contains $n + 2$ lines.

The first line contains an integer $n$, indicating that there are $n$ carpets in total.

Each of the next $n$ lines, the $(i+1)$-th line, describes carpet $i$ with four integers $a, b, g, k$, separated by single spaces, representing the coordinates of the lower-left corner $(a, b)$ and the lengths of the carpet in the $x$- and $y$-directions, respectively.

The $(n + 2)$-th line contains two integers $x$ and $y$, representing the coordinates $(x, y)$ of the query point.

Output Format

Output a single line containing one integer, the index of the required carpet; if the point is not covered by any carpet, output -1.

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

3

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

-1

Hint

[Sample Explanation 1]

As shown in the figure, carpet $1$ is drawn with solid lines, carpet $2$ with dashed lines, and carpet $3$ with double solid lines. The topmost carpet covering the point $(2, 2)$ is carpet $3$.

[Data Range]

• For $30\%$ of the data, $n \le 2$.
• For $50\%$ of the data, $0 \le a, b, g, k \le 100$.
• For $100\%$ of the data, $0 \le n \le 10^4$, $0 \le a, b, g, k \le 10^5$.

NOIP 2011 Senior Day 1 Problem $1$.

Translated by ChatGPT 5