Move that Mouse AGAIN

Time limit3sMemory limit128 MB

Summary

Given up to 50,000 axis-aligned rectangles in a fixed bottom-to-top stacking order, process 50,000 point clicks, printing the topmost window at each point and moving it to the top of the stack.

Level: Hard9 of 10
Topics: Segment tree, Geometry, Sorting, Implementation
Solved: No attempts yet

Problem

You have a screen with $R$ rows and $C$ columns, where $1 \le R \le 10{,}000$ and $1 \le C \le 10{,}000$ .

There are $n$ ( $1 \le n \le 50{,}000$ ) rectangular windows. Window $i$ is described by its top-left corner $(x_l, y_t)$ and its bottom-right corner $(x_r, y_b)$ , and you may assume $1 \le x_l < x_r \le C$ and $1 \le y_b < y_t \le R$ (so no window is empty). A window includes every point on its border: it contains exactly the points $(x, y)$ with $x_l \le x \le x_r$ and $y_b \le y \le y_t$ .

The windows are given in stacking order from bottom to top: wherever two windows overlap, the one listed later in the input is drawn on top of the earlier one (not necessarily immediately after it). Windows are numbered $1$ to $n$ in input order.

A mouse can click on the screen. It receives $m$ ( $1 \le m \le 50{,}000$ ) instructions; each instruction moves the mouse to a position $(x, y)$ with $1 \le x \le C$ and $1 \le y \le R$ and clicks there. When the mouse clicks, the window that is visible at that position — the topmost window covering it — is moved to the very top, becoming fully visible and the focused window. If no window covers that position, the stacking order is unchanged.

After each click, report which window that click brought into focus.

Input

The first line contains the integer $C$ , the number of columns. The second line contains the integer $R$ , the number of rows. The third line contains the integer $n$ , the number of windows.

Each of the next $n$ lines contains four integers $x_l$ , $y_t$ , $x_r$ , $y_b$ — the top-left and bottom-right coordinates of a window. The windows are numbered $1$ to $n$ in this order.

The next line contains the integer $m$ . Each of the next $m$ lines contains two integers $x$ and $y$ , the new position of the mouse for that click.

Output

Print $m$ lines. The $i$ -th line contains an integer $v_i$ with $0 \le v_i \le n$ : if $v_i > 0$ , then click $i$ landed on window $v_i$ and moved it to the top; if $v_i = 0$ , then click $i$ was on a position with no window.

Hint

As an illustration of the rule: on a $200$ -wide, $100$ -tall screen holding three windows, a click at $(60, 20)$ falls on window $1$ and raises it to the top; a click at $(150, 90)$ touches no window, so $0$ is reported; a click at $(150, 30)$ falls on window $2$ and raises it to the top.

Examples3

Example 1

Input

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

Expected output

1
0
2

Example 2
Input
```
10
10
1
2 8 5 3
3
2 3
1 1
5 8
```
Expected output
```
1
0
1
```

Example 3

Input

Expected output