F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Windows

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 269    Accepted Submission(s): 27


Problem Description
Consider the following scenario. The screen has width 200 and height 100. There are three windows on the screen.



The left picture shows the initial configuration. Windows are drawn from bottom to top, according to the ID, so window 1 is at the bottom, and window 3 is at the top. The right picture shows the screen after clicking at (60, 20). Point (60, 20) is in the visible part of window 1, so it is brought to the top (each time a window is clicked, it gets focus, and brought to the top. The relative order of other windows won¡¯t change). If you then click at (150, 90), nothing will change, since it is not within the visible part of any window. Then, after clicking at (150, 30), window 2 will get focus. Note that, each window includes all points on its borders: if its top-left corner and bottom-right corner are (x1,y1) and (x2,y2) respectively, it includes exactly the points (x, y) such that x1 <= x <= x2, y2 <= y <= y1.
Your task is to determine, for each click, the ID of window which is just clicked on (or 0 if no window is clicked).
 

Input
There will be only one case, beginning with two integer numbers C and R (1 <= C, R <= 10000), the number of columns and rows, respectively. The third line contains an integer n (1 <= n <= 50000), the number of windows. On each of the next n lines, there are four integers x1, y1, x2, y2, the top-left and bottom-right coordinates of the window. The window is non-empty (i.e. x1 < x2, y2 < y1).The window IDs are 1, 2, 3, ¡­, n, in the order they appear in the input. On the next line, there is an integer m (1 <= m <= 100000), the number of mouse clicks. On each of the next m lines, there will be two integers x and y, the coordinate clicked. In the judge input, all the coordinates (x, y) will be randomly generated within the screen (i.e. 1 <= x <= C, 1 <= y <= R).
 

Output
For each click, print the window ID being clicked. If there is no window get clicked, print 0. Output a blank line after each test case.
 

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
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-05-12 16:24:08, Gzip enabled