32356번 - 패러글라이딩 스페셜 저지

문제

하넬은 패러글라이딩 대회에 사진을 찍으러 가기로 했다. 대회에는 $N$대의 패러글라이더가 준비되어 있다. $i$번째 패러글라이더는 기준선으로 부터 $x_i$ 만큼 왼쪽으로 떨어진 곳에서 $y_i$ 높이에서 시작하여 오른쪽 방향으로 포물선 궤적을 그리면서 비행한다. $i$번째 패러글라이더가 기준선으로부터 오른쪽으로 $x$만큼 떨어져있을 때 패러글라이더의 높이는

$$y_i-\dfrac{1}{c}(x+x_i)^2$$

로 주어지며, $c$는 모든 패러글라이더가 공유하는 중력과 속도에 관한 상수이다. 패러글라이더는 비행을 하다가 높이가 0ドル$이 되는 순간 즉시 멈춘다.

$c=100$일 때의 $(x_1, y_1) = (10, 30)$인 빨간색 패러글라이더와 $(x_2, y_2) = (25, 40)$인 파란색 패러글라이더의 궤적.

또, 패러글라이더의 궤적이 너무 많이 겹치면 사고가 일어나기 쉽기 때문에 기준선 오른쪽 구간에서 패러글라이더의 궤적은 완전히 겹치는 일이 발생하지 않도록 사전에 배치되어 있다.

하넬은 $Q$개의 사진을 기준선에서 오른쪽으로 $p_1,ドル $\cdots,ドル $p_Q$ 만큼 떨어진 위치에서 찍고자 한다. 하넬은 각 $p_i$ 별로 가장 높이 있는 패러글라이더의 높이를 계산해서 완벽한 구도로 사진을 찍고자 하지만 아쉽게도 다른 사진들을 편집하느라 바쁘다. 바쁜 하넬을 대신해서 각 $p_i$ 별로 가장 높이 있는 패러글라이더의 높이를 구해주자.

입력

첫 번째 줄에 패러글라이더의 개수 $N$과 찍을 사진의 개수 $Q$가 주어진다. $(1 \le N, Q \le 300,000円)$

두 번째 줄에 패러글라이더의 포물선 궤적의 계수 $c$가 주어진다. $(1 \le c \le 10^6)$

$N$개의 줄에 걸쳐서 패러글라이더의 위치 $x_i,ドル $y_i$가 공백으로 구분되어 주어진다. $(1 \le x_i \le 10^9;$ 1ドル \le y_i \le 10^{12})$

마지막 줄에 $p_1, p_2, \cdots, p_Q$가 공백으로 구분되어 주어진다. $(1 \le p_i \le 10^9)$

기준선 오른쪽 구간에서 패러글라이더의 궤적이 완전히 겹치는 경우는 주어지지 않는다.

입력으로 주어지는 모든 수는 정수이다.

출력

$i$번째 줄에 $p_i$ 위치에서 가장 높이 날고 있는 패러글라이더의 높이를 출력한다.

기준선 오른쪽 $p_i$ 위치에 도달하는 패러글라이더가 없을 경우 0ドル$을 출력한다.

정답과 상대오차 또는 절대오차가 10ドル^{-9}$ 이하라면 정답으로 처리된다.

제한

힌트