AT_abc472_f [ABC472F] Centroid of a Slice

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).

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

### Sample Explanation 1 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) $ . ### 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.