2005 Canadian Computing Competition, Stage 2

Day 2, Problem 3: Move that Mouse AGAIN

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 ≤ R ≤ 10000) rows and C (1 ≤ C ≤ 10000) columns. You have n (1 ≤ n ≤ 50000) rectangular windows, defined by the "top-left" coordinates (xl, yt) and "bottom-right" coordinates (xr, yb). Note that you can assume that 1 ≤ xl < xr ≤ C and 1 ≤ yb < yt ≤ 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 (xl, yt) and (xr, yb) includes exactly the points (x, y) such that xl ≤ x ≤ xr and yb ≤ y ≤ yt.

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 to be told to move to a particular position (say (x, y), where 1 ≤ xC and 1 ≤ yR) 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 ≤ m ≤ 10000) 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 xl followed by yt followed by xr followed by yb, 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 vi such that 0 ≤ vi ≤ n. If line i contains the integer vi (vi > 0), that indicates that after the ith mouse move, the window vi was just clicked on (and has moved to the top). If, instead, vi = 0, then there was no window at that position.

Sample Input

50 50 80 20
70 60 180 10
10 90 100 40
60 20
150 90
150 30

Sample Output



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.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 5.00s
Memory Limit: 256M
Added: Dec 23, 2008

Languages Allowed:

Comments (Search)

It's quiet in here...