Problem Statement

There is a convex $N$-gon $P$ on the $xy$-plane. The vertices of $P$ are numbered $1,2,\dots,N$ counterclockwise, and the coordinates of vertex $i$ are $(x_i,y_i)$.

Answer $Q$ questions.

The $j$-th question gives two distinct vertices $u_j$ and $v_j$. Here, the vertices $u_j$ and $v_j$ are not adjacent on the boundary of $P$.

The segment connecting vertices $u_j$ and $v_j$ divides $P$ into two polygons; let $P'$ be the one lying to the right of the directed line from vertex $u_j$ to vertex $v_j$. Find the coordinates of the geometric center of $P'$ (the centroid obtained by regarding the interior of the polygon as a thin plate of uniform density).

Constraints

• $4 \leq N \leq 3 \times 10^4$
• $1 \leq Q \leq 2 \times 10^5$
• $|x_i|,|y_i| \leq 5 \times 10^5$
• $(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$ form a convex polygon in counterclockwise order.
• All interior angles of $P$ are less than $180$ degrees.
• $1 \leq u_j,v_j \leq N$
• $u_j \neq v_j$
• Vertices $u_j$ and $v_j$ are not adjacent on the boundary of $P$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$ $Q$
• $x_1$ $y_1$
• $x_2$ $y_2$
• $\vdots$
• $x_N$ $y_N$
• $u_1$ $v_1$
• $u_2$ $v_2$
• $\vdots$
• $u_Q$ $v_Q$

Output

Output $Q$ lines. On the $j$-th line, letting $(p_j,q_j)$ be the coordinates of the answer to the $j$-th question, output $p_j$ and $q_j$ in this order, separated by a space.

The answer is considered correct if, for each of $p_j$ and $q_j$, its absolute or relative error from the true value is at most $10^{-6}$.

5 4
4 1
1 3
-3 2
-1 -2
2 -1
2 4
5 3
1 4
4 2

-1.000000000000000 1.000000000000000
0.864197530864198 1.209876543209877
0.198198198198198 0.828828828828829
1.391304347826087 0.434782608695652

For the first question, $P'$ is the triangle with vertices $(1,3),(-3,2),(-1,-2)$, and its geometric center is $(-1,1)$.

For the second question, $P'$ is the quadrilateral with vertices $(2,-1),(4,1),(1,3),(-3,2)$, and its geometric center is $\left(\frac{70}{81},\frac{98}{81}\right)$.

10 10
480451 142016
404696 274257
7097 390813
-134582 195390
-167108 143104
-359470 -180367
-406293 -273476
74335 -494832
486873 -391664
493159 -292349
5 8
8 6
5 2
5 1
10 3
1 7
3 5
2 5
4 9
1 8

-167917.431926206833203 -207268.968943785114349
126221.026579795702381 -68771.715180365014040
111801.954824466955586 -124063.178438661167072
99590.935535112756283 -153792.378227918737825
321662.353363423237819 113722.100435559268610
43574.061369374611386 102411.022160871806300
-98197.666666666666667 243102.333333333333333
79984.488622522356481 269160.678085376751920
-3267.792578363696043 -210454.379232334372417
46257.363593155145794 -38546.483790939251583

• Source: AtCoder ABC 472 F