평면 늘리기

이고르는 기하학을 매우 좋아해서 $n$개의 서로 다른 점으로 이루어진 집합 $P$와 함께 평면을 샀다. $i$번째 점은 $(x_i, y_i)$에 있다.

이고르는 서로 가장 멀리 떨어진 두 점을 아주 쉽게 찾을 수 있었다. 싫증이 난 그는 실수 $\alpha_1, \alpha_2, \alpha_3, \ldots, \alpha_q$를 $q$개 골랐다. 각 $\alpha_j$에 대해, 모든 점의 $x$좌표에 $\alpha_j$를 곱한 뒤 두 점 사이 거리의 최댓값을 구하려 한다. 형식적으로는 집합 $(x_i \cdot \alpha_j, y_i)$에서 가장 멀리 떨어진 두 점을 찾는 문제이다.

첫 줄에 두 정수 $t$와 $g$가 주어진다 ($1 \le t \le 250\,000$, $0 \le g \le 9$). $t$는 테스트 케이스의 수이고, $g$는 테스트 케이스가 만족할 수 있는 추가 조건을 나타내는 그룹 번호이다. 이어서 $t$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 정수 $n$과 $q$ ($2 \le n \le 500\,000$, $1 \le q \le 500\,000$)로 시작한다. 각각 점의 수와 질의의 수이다. 다음 $n$개 줄에는 점의 좌표 $x_i$와 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)가 주어진다. 한 테스트 케이스 안의 점들은 모두 서로 다르다. 다음 $q$개 줄에는 각각 배율인 실수 $\alpha_j$ ($1 \le \alpha_j \le 10^9$) 하나가 주어진다.

$n_i$의 합을 $N$, $q_i$의 합을 $Q$라 하면 $N, Q \le 500\,000$이 보장된다.

각 테스트 케이스마다 $q$개의 실수를 출력한다. 질의마다 답을 입력 순서대로 적는다. 정답을 $b$, 출력한 답을 $a$라 할 때 $\frac{|a-b|}{\max(b,1)} \le 10^{-6}$을 만족하면 정답으로 인정한다.