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}$.