Plane stretching

문제

Igor is a big fan of geometry, so he bought himself a plane together with a set $PP$ of $nn$ distinct points, $ii$-th of them is located at $(x_i,y_i)(x\_i,y\_i)$.

It was extremely easy for Igor to find two points among them furthest away from each other. He quickly got bored and decided to come up with $qq$ real numbers ${\alpha }_1\backslash alpha\_1$, ${\alpha }_2\backslash alpha\_2$, ${\alpha }_3\backslash alpha\_3$, $\dots \backslash ldots$, ${\alpha }_q\backslash alpha\_q$. For each of these numbers Igor is interested in the maximum possible distance between any two of the points if he scales the $xx$-coordinate of each point by ${\alpha }_j\backslash alpha\_j$. Formally speaking, he is interested in finding the two furthest points in a set $(x_i\cdot {\alpha }_j,y_i)(x\_i\; \backslash cdot\; \backslash alpha\_j,\; y\_i)$. Please help Igor!

입력

Each input contains multiple test cases. The first line contains two integers $tt$ and $gg$ ($1\le t\le 2500001\; \backslash le\; t\; \backslash le\; 250\backslash ,000$, $0\le g\le 90\; \backslash le\; g\; \backslash le\; 9$) --- the number of test cases and the group number to indicate additional constraints those test cases might satisfy. Then $tt$ test cases follow.

Each test case starts with two integers $nn$ and $qq$ $(2\le n\le 500000,1\le q\le 500000)(2\; \backslash le\; n\; \backslash le\; 500\backslash ,000,\; 1\; \backslash le\; q\; \backslash le\; 500\backslash ,000)$ --- the number of points and the number of queries.

The following $nn$ lines contain the coordinates of each point $x_{i}x\_i$ and $y_{i}y\_i$ $(-{10}^9\le x_i,y_i\le {10}^9)(-10^9\; \backslash le\; x\_i,\; y\_i\; \backslash le\; 10^9)$. It is guaranteed that all points within a test case are distinct.

The following $qq$ lines contain the queries, each of them is identified by a single real number ${\alpha }_j\backslash alpha\_j$ $(1\le {\alpha }_j\le {10}^9)(1\; \backslash le\; \backslash alpha\_j\; \backslash le\; 10^9)$ --- the scaling coefficients.

Let us denote the sum of values $n_{i}n\_i$ among all test cases as $NN$, and the sum of values $q_{i}q\_i$ as $QQ$. It is guaranteed that $N,Q\le 500000N,\; Q\; \backslash le\; 500\backslash ,000$.

출력

For each test case output $qq$ real numbers: the answer to $ii$-th query. Your answer will be accepted if its absolute or relative error does not exceed ${10}^{-6}10^\{-6\}$. More precisely, if $aa$ is your answer, and $bb$ is the judges' answer, then your answer will be considered correct in case $\frac{\mathrm{\mid }a-b\mathrm{\mid }}{\max (b,1)}\le {10}^{-6}\backslash frac\{|a-b|\}\{\backslash max(b,1)\}\; \backslash le\; 10^\{-6\}$.

2 0
5 2
0 0
1 1
0 2
-1 3
0 4
1
2.5
8 4
0 0
6 11
7 13
4 14
0 15
-4 14
-7 13
-6 11
2
1
1.25
1.5

4.000000
5.385165
28.000000
15.000000
17.500000
21.000000