Cybercrime Donut Investigation#3066
Year 2042. The Internet has evolved into a virtual reality dataspace where crimes are committed every day. The 2041 SWERC winner developed an agent that drops a donut every time a crime is committed in Cyberspace. Each donut has its own unique signature. The Madrid Police have a large database of crimes and their donut signatures.
Today is your day. Your task is to implement a new agent that searches the database for records that most closely resemble the signature of a donut found at a new crime scene.
Figure 2: The major piece of evidence for today's unsolved crime streak
Experts in virtual criminology have determined the best similarity measure between donuts: compute the difference in radius of the internal part of the toroids (holes), compute the difference in radius of the external part of the toroids (tubes), and then add these differences.
The first line of each test case contains (1 \leq n \leq 100000), the number of donuts in the database. Each of the following lines contains the radius of the hole and the radius of the tube of the -th donut in the database, described by two integers and (1 \leq l, w \leq 10^9). After that, there is a line containing (1 \leq q \leq 50000), the number of donuts that you are looking for in the database. Then lines follow, each describing the dimensions of a newly found donut in the same way.
Different test cases are separated by a blank line. A line containing marks the end of the input.
The output for each test case should contain lines, each with one integer. The -th line should contain the similarity between the -th newly found donut and the donut in the database that most closely resembles it. Outputs for different test cases should be separated by a blank line.
Example 1