Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a convex polygon with N sides. You have to answer Q queries. The i^{th} query is described by two integers v_{i}, t_{i}. In this query, all sides of the polygon start moving parallel to their respective perpendicular vector away from the centroid with a constant velocity of $v_{i} \frac{units}{sec}$. Output the final area covered by N sides of the polygon after time t_{i} seconds.

For each query, consider the initial coordinates of vertices of the given polygon.

Note:
Since the input-output is large, prefer using fast input-output methods.
The problem requires high precision, so prefer using data types with a precision equivalent to long double in C++.

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• Each testcase contains N + Q + 1 lines of input.
• The first line of each test case contains two space-separated integers N, Q.
• N lines follow. For each valid i, the i^{th} of these lines contains two space-separated integers x_{i}, y_{i}, coordinates of the i^{th} vertex of the polygon.
• Next Q lines follow. For each valid i, the i^{th} of these lines contains two space-separated integers v_{i}, t_{i}, description of the i^{th} query.

------ Output Format ------

For each query, output in a single line the final area covered by N sides of the polygon.

Your answer will be considered correct if its relative or absolute error does not exceed 10^{-2}.

------ Constraints ------

$1 ≤ T ≤ 250$
$3 ≤ N ≤ 10^{4}$
$1 ≤ Q ≤ 10^{4}$
$0 ≤ x_{i}, y_{i} ≤ 2 \cdot 10^{6}$
$1 ≤ v_{i}, t_{i} ≤ 10^{5}$
$1 ≤ v_{i} \cdot t_{i} ≤ 10^{5}$
- The sum $N$ over all testcases does not exceed $5 \cdot 10^{5}$.
- The sum $Q$ over all testcases does not exceed $5 \cdot 10^{5}$.
- The vertices of polygon are given in counter-clockwise order.
- The internal angles of the given polygon are greater than $1^{\circ}$.

------ subtasks ------

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------
2
4 1
1 1
2 1
2 2
1 2
1 1
3 2
1 1
2 1
1 2
1 1
2 3
----- Sample Output 1 ------
9.0000000
9.7426406
230.8086578
----- explanation 1 ------
Below are the images for the respective test cases. Inner polygons are the ones at the start and the rays represent the distance traveled by the sides at the given speed in a given time. Outer polygons denote the final ones after the movements of the sides.

Test case $1$:

Test case $2$: $1^{st}$ query

见题面

见题面