Cyber Donut Crime Investigation

By the year 2042, the internet has advanced far enough to create virtual reality, and cyber crimes happen every day. To fight them, the winner of the 2041 SWERC contest built an agent that drops a single donut at the scene whenever a cyber crime occurs. Every donut carries a unique id, and the Madrid Police Department keeps a large database that stores each crime together with the unique id of the donut left at its scene.

Today is your day. Your mission is to develop a new agent that reads the records stored in the database and finds the donut most similar to the one at a new crime scene.

Virtual-criminology experts proposed the criterion for judging how similar two donuts are: their similarity is the absolute difference of their hole radii plus the absolute difference of their outer radii. That is, writing $l$ for the hole radius and $w$ for the outer radius, the similarity of two donuts $(l_1, w_1)$ and $(l_2, w_2)$ is $|l_1 - l_2| + |w_1 - w_2|$. A smaller value means the two donuts are more alike.

The input consists of several test cases.

The first line of each test case contains the number of donuts stored in the database, $n$ ($1 \le n \le 100\,000$).

Each of the next $n$ lines contains two integers, the hole radius $l$ and the outer radius $w$ of one database donut ($1 \le l, w \le 10^9$).

The next line contains $q$, the number of donuts to look up ($1 \le q \le 50\,000$).

Each of the next $q$ lines contains two integers, the hole radius and outer radius of one donut to look up.

Consecutive test cases are separated by a blank line, and a single line containing $-1$ marks the end of the input.

For each test case, print $q$ lines. The $i$-th line must contain, as an integer, the similarity between the $i$-th queried donut and the most similar (smallest-similarity) donut in the database.

The outputs of different test cases must be separated by a single blank line.