By IX Maratona de Programação IME-USP, 2005 Brazil
Texas is famous for its excellent quality meat. "Steaks" with up to two inches thick roasted in grills are a culinary specialty of the state. In San Antonio is difficult to find pizza delivery by phone, but it is very common to find "steaks disk". You call the number and in few minutes there comes a succulent steak at home, hot and ready to eat. It is clear that such efficiency depends on a complicated delivery system. There are several headquarters throughout the city, and whenever a call is done the nearest headquarter is put in action, the steak is roasted and delivery follows with succulent dinner. We know that San Antonio is a planned city. We can imagine the crosses city as vertices of a grid. For some obscure reason, all headquarters are installed at crosses. Your task is to help the company to deliver the steaks.
Several instances are given. For each instance are given the dimensions 0 ≤ M, N ≤ 1000 of the city (will be a grid with M lines and N columns). An N = 0 or M = 0 value indicates the end of data. Next comes the number 0 < K ≤ 100000 of the headquarters. In the following K lines have the coordinates of the headquarters. Next is the number 0 ≤ L ≤ 100000 of calls requesting steaks. In the following L lines have the coordinates of each call position (which are also the vertices of the grid).
For each solved instance, you should print an identifier Instance H where H is an integer, sequential and growing from 1 number. In the following L lines, you should print in which headquarter the corresponding request was attended to that line. In case of more than one headquarter at the same distance, give preference that owning the lowest line index. If the draw persists, give preference to the lowest column index. A blank line should separate the output of each instance.
|Sample Input||Sample Output|