22374번 - Mountain View 스페셜 저지다국어

Mr. Mt. is eager to take photos of mountains all over the world. Today, Mr. Mt. visits one of the most interesting mountain ranges, the Alps of Curved Mountains. The shape of all the mountains of the Alps of Curved Mountains is, surprisingly, hemisphere.

Mr. Mt. just decided the place from where he will take photos of the mountains. The area covering the mountains is flat, horizontal ground, and the place he chose is far enough from the mountains. Hence the mountains look like two-dimensional semicircles in a row, where all the straight segments of the semicircles are aligned with a straight line. Some of them may be overlapped or completely covered by other semicircles.

Mr. Mt. is waiting for the sunset. After sunset, the mountains should be in shadow and cannot be distinguished. In that situation, Mr. Mt. is interested in how the photos will look like. You, his camera assistant, are also a great programmer. Given the coordinates and radiuses of all the semicircles, he asks you to write a program to calculate the heights of the 2D shadow at the positions he wants to know.

Figure F-1 illustrates the mountains of Sample 2. The first, second, third mountains are overlapped, and the fifth mountain is covered by the fourth mountain. Figure F-2 shows the mountains in shadow. For example, at position 82, there are the fourth and fifth mountains, and the shadow's height is the highest of them, the height of the fourth mountain.

Figure F-1. Mountains of Sample 2

Figure F-2. Mountains in shadow and positions of Sample 2

The input consists of a single test case in the format below.

$N$

$c_1$ $r_1$

$\vdots$

$c_N$ $r_N$

$Q$

$x_1$

$\vdots$

$x_Q$

The first line contains a single integer $N$ ($1 \le N \le 10^5$), where $N$ is the number of mountains of the Alps of Curved Mountains. The $i$-th of the following $N$ lines contains two integers $c_i$ ($1 \le c_i \le 10^8$) and $r_i$ ($1 \le r_i \le 10^8$). $c_i$ is the position of the center of the $i$-th semicircle in a straight line, where "center" means the center of the circle made by reflecting the semicircle on the straight segment of the semicircle. $r_i$ is the radius of the $i$-th semicircle. The following line contains a single integer $Q$ ($1 \le Q \le 10^5$), where $Q$ is the number of the positions on a straight line Mr. Mt. is interested in. The $j$-th of the following $Q$ lines contains a single integer $x_j$ ($1 \le x_j \le 10^8$), where $x_j$ is the $j$-th position on a straight line Mr. Mt. is interested in.

Output $Q$ lines, the $j$-th of which is the height of the shadow of the mountains at the $j$-th position Mr. Mt. is interested in. Absolute or relative errors less than $10^{-7}$ are permissible.