| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 5 | 1 | 1 | 25.000% |
You probably remember from Stage 1ドル$ that computers have a mouse and sometimes, if you really have to, you have a bunch of windows that you can click on.
In particular, you will have a screen which has $R$ $(1 \le R \le 10,000円)$ rows and $C$ $(1 \le C \le 10,000円)$ columns. You have $n$ $(1 \le n \le 50,000円)$ rectangular windows, defined by the "top-left" coordinates $(x_l, y_t)$ and "bottom-right" coordinates $(x_r, y_b)$. Note that you can assume that 1ドル \le x_l < x_r \le C$ and 1ドル \le y_b < y_t \le R$ (thus, you don't have empty windows).
It is worth noting that a window includes all points on its borders: that is, the window defined by $(x_l, y_t)$ and $(x_r, y_b)$ includes exactly the points $(x, y)$ such that $x_l \le x \le x_r$ and $y_b \le y \le y_t$.
If two windows overlap, the one which is on top of the other window will be listed later in the sequence (not necessarily immediately after, however). Here comes the mouse part.
You also have a mouse that can click on windows. Initially, the mouse is at position $(1, 1)$ (the bottom-left corner of the screen). The mouse will then be told to move to a particular position (say $(x, y),ドル where 1ドル \le x \le C$ and 1ドル \le y \le R$) and click. When the mouse clicks, the window which is visible at that position moves to the top (that is, the entire window becomes visible, possibly hiding some other windows). There will be $m$ $(1 \le m \le 50,000円)$ such mouse clicks.
Your job is to indicate which of the $n$ windows is "in focus" (i.e., most recently clicked on) after each mouse move.
The first line of input consists of an integer $C,ドル the number of columns. The second line of input consists of an integer $R,ドル the number of rows. The third line of input consists of the number $n,ドル the number of windows. On each of the next $n$ lines, there are four integers $x_l$ followed by $y_t$ followed by $x_r$ followed by $y_b,ドル indicating the "top-left" and "bottom-right" coordinates of this window. (These windows are numbered from 1ドル$ to $n$). On the next line is the integer $m$. On each of the next $m$ lines will be two integers, $x$ followed by $y,ドル indicating the new position of the mouse.
The output is $m$ lines long, each line containing an integer $v_i$ such that 0ドル \le v_i \le n$. If line $i$ contains the integer $v_i$ $(v_i > 0),ドル that indicates that after the $i$th mouse move, the window $v_i$ was just clicked on (and has moved to the top). If, instead, $v_i = 0,ドル then there was no window at that position.
200 100 3 50 50 80 20 70 60 180 10 10 90 100 40 3 60 20 150 90 150 30
1 0 2
The screen has width 200ドル$ and height 100ドル$. There are three windows on the screen, and initially, we have the following configuration:
After the mouse clicks at $(60, 20),ドル we have:
Since there is no window at position $(150, 90),ドル 0ドル$ is outputted. Once we click at position $(150, 30),ドル that moves window 2ドル$ into focus, to get the following picture.