산맥의 그림자

Mt. 씨는 전 세계의 산을 사진으로 담고 싶어 한다. 오늘 Mt. 씨는 가장 흥미로운 산맥 중 하나인 Curved Mountains의 알프스를 찾았다. Curved Mountains의 알프스에 있는 모든 산의 모양은 놀랍게도 반원이다.

Mt. 씨는 방금 산을 촬영할 장소를 정했다. 산을 둘러싼 지역은 평평한 수평 지면이고, 그가 고른 장소는 산에서 충분히 멀리 떨어져 있다. 따라서 산은 일직선으로 늘어선 2차원 반원처럼 보이며, 모든 반원의 지름은 하나의 직선 위에 놓여 있다. 일부 반원은 서로 겹치거나 다른 반원에 완전히 가려질 수 있다.

Mt. 씨는 해가 지기를 기다리고 있다. 해가 진 후 산은 그림자에 들어가 구분할 수 없게 된다. 그 상황에서 Mt. 씨는 사진이 어떻게 보일지 궁금해한다. 그의 카메라 조수인 당신도 훌륭한 프로그래머다. 모든 반원의 좌표와 반지름이 주어졌을 때, 그가 알고 싶어 하는 위치에서 2차원 그림자의 높이를 계산하는 프로그램을 작성하라는 요청을 받았다.

그림 F-1은 Sample 2의 산들을 나타낸다. 첫 번째, 두 번째, 세 번째 산은 서로 겹쳐 있고, 다섯 번째 산은 네 번째 산에 가려져 있다. 그림 F-2는 그림자 속의 산들을 나타낸다. 예를 들어 위치 82에는 네 번째와 다섯 번째 산이 있고, 그림자의 높이는 그중 가장 높은 네 번째 산의 높이이다.

그림 F-1. Sample 2의 산들

그림 F-2. 그림자 속의 산들과 Sample 2의 위치들

입력은 아래 형식의 단일 테스트 케이스로 구성된다.

$N$

$c_1$ $r_1$

$\vdots$

$c_N$ $r_N$

$Q$

$x_1$

$\vdots$

$x_Q$

첫째 줄에는 정수 $N$ ($1 \le N \le 10^5$)이 주어지며, $N$은 Curved Mountains의 알프스에 있는 산의 수이다. 다음 $N$개 줄 중 $i$번째 줄에는 두 정수 $c_i$ ($1 \le c_i \le 10^8$)와 $r_i$ ($1 \le r_i \le 10^8$)가 주어진다. $c_i$는 $i$번째 반원의 중심 위치이며, 여기서 "중심"은 반원을 그 지름에 대해 반사시켜 얻은 원의 중심을 뜻한다. $r_i$는 $i$번째 반원의 반지름이다. 다음 줄에는 정수 $Q$ ($1 \le Q \le 10^5$)가 주어지며, $Q$는 Mt. 씨가 궁금해하는 직선 위의 위치의 수이다. 다음 $Q$개 줄 중 $j$번째 줄에는 정수 $x_j$ ($1 \le x_j \le 10^8$)가 주어지며, $x_j$는 Mt. 씨가 궁금해하는 $j$번째 위치이다.

$Q$개 줄을 출력하며, $j$번째 줄에는 Mt. 씨가 궁금해하는 $j$번째 위치에서 산 그림자의 높이를 출력한다. 절대 오차 또는 상대 오차가 $10^{-7}$ 미만이면 정답으로 인정된다.