H. Humpty Dumpty
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Humpty Dumpty is on the top of his wall. Humpty Dumpty will have some great falls.

The wall can be represented as a two dimensional grid of cells, where $$$(x, y)$$$ denotes a cell in the $$$x$$$-th column from the left of the grid, and $$$y$$$-th row from the bottom of the grid. Some of the cells are fully occupied by 1x1 platforms that fill the entirety of the cell. In particular, any cell of the form $$$(x, 0)$$$ contains a platform. There are also $$$n$$$ additional platforms at other locations.

Humpty Dumpty begins in some cell that isn't occupied by a platform. He may or may not begin directly above a cell with a platform. Humpty's journey follows the following process:

  • Suppose Humpty is in cell $$$(x, y)$$$. He will then fall to cell $$$(x, y_2)$$$ such that $$$(x, y_2-1)$$$ contains a platform and none of the cells of the form $$$(k, y)$$$ where $$$y_2 \leq k \leq y$$$ contain a platform. It can be proven that there is exactly one $$$y_2$$$ that satisfies this condition. The ouch factor of his fall is equal to the distance he falls, which is $$$y - y_2$$$.
  • Suppose Humpty is now in cell $$$(x, y)$$$. If there is a platform in both cells $$$(x-1, y)$$$ and $$$(x+1, y)$$$, Humpty ends his journey. Otherwise, Humpty must move to either cell $$$(x-1, y)$$$ (if it is not occupied by a platform) or $$$(x+1, y)$$$ (if it is not occupied by a platform). Note that it is possible for Humpty's journey to continue forever.

Humpty's total ouch factor is defined as the maximum ouch factor over all of the falls he makes during his journey.

You are given $$$q$$$ queries. In the $$$i$$$-th query, Humpty will start in the cell $$$(x_i, y_i)$$$. Please find the maximum and minimum total ouch factor across all of the possible paths that Humpty could take in his journey.

Input

The first line contains $$$n$$$, the number of platforms on the wall. $$$0 \leq n \leq 10^5$$$.

The next $$$n$$$ lines contain two integers, $$$x, y$$$, the horizontal and vertical coordinate of the platform. $$$1 \leq x, y \leq 10^5$$$.

The next line contains $$$q$$$, the number of queries. $$$1 \leq q \leq 5 \cdot 10^4$$$.

The next $$$q$$$ lines contain two integers, $$$x, y$$$, the horizontal and vertical coordinate of Humpty's starting point. $$$1 \leq x, y \leq 10^5$$$.

It is guaranteed that all platforms are unique. It is also guaranteed that all query spots are not wall spots.

Output

Output $$$q$$$ lines, with each line containing two integer, the maximum and minimum distance Humpty could fall if he started at the corresponding location.

Examples
Input
4
1 4
2 3
3 1
3 6
4
1 5
2 4
3 7
1 3
Output
4 2
2 2
6 3
2 2
Input
5
1 4
2 3
3 3
4 3
5 4
3
1 5
5 7
3 4
Output
4 1
4 2
0 0
Note

For the first sample:

Starting @ $$$(1, 5)$$$: Maximum fall: $$$\textbf{(1, 5)} \rightarrow (0, 1)$$$ Minimum fall: $$$(1, 5) \rightarrow \textbf{(2, 4)} \rightarrow (3, 2) \rightarrow (2, 1)$$$

Starting @ $$$(2, 4)$$$: Maximum fall: $$$\textbf{(2, 4)} \rightarrow (3, 2) \rightarrow (2, 1)$$$ Minimum fall: $$$\textbf{(2, 4)} \rightarrow (3, 2) \rightarrow (2, 1)$$$

Starting @ $$$(3, 7)$$$: Maximum fall: $$$\textbf{(3, 7)} \rightarrow (4, 1)$$$ Minimum fall: $$$\textbf{(3, 7)} \rightarrow (2, 4) \rightarrow (3, 2) \rightarrow (2, 1)$$$

Starting @ $$$(1, 3)$$$: Maximum fall: $$$\textbf{(1, 3)} \rightarrow (1, 1)$$$ Minimum fall: $$$\textbf{(1, 3)} \rightarrow (1, 1)$$$

Bold shows the maximum single fall in each of the sequences, which is also the determining height for the answer.