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 (x_l, y_t) and "bottom-right" coordinates (x_r, y_b). Note that you can assume that 1 ≤ x_l < x_r ≤ C and 1 ≤ y_b < y_t ≤ 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 ≤ x ≤ x_r and y_b ≤ y ≤ 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 to be told to move to a particular position (say (x, y), where 1 ≤ x ≤ C and 1 ≤ y ≤ 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 ≤ 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.

Input

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.

Output

The output is m lines long, each line containing an integer v_i such that 0 ≤ v_i ≤ n. If line i contains the integer v_i (v_i > 0), that indicates that after the ith 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.

Sample Input

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

Sample Output

1
0
2

Explanation

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:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)