AT_abc472_f [ABC472F] Centroid of a Slice

$ xy $ 平面上に凸 $ N $ 角形 $ P $ があります。 $ P $ の頂点には反時計回りに頂点 $ 1,2,\dots,N $ と番号が付けられており、頂点 $ i $ の座標は $ (x_i,y_i) $ です。 $ Q $ 個の質問に答えてください。 $ j $ 番目の質問では、相異なる $ 2 $ 頂点 $ u_j,v_j $ が与えられます。 ただし頂点 $ u_j,v_j $ は $ P $ の周上において隣り合いません。 頂点 $ u_j $ と頂点 $ v_j $ を結ぶ線分で $ P $ を二つの多角形に分割し、頂点 $ u_j $ から頂点 $ v_j $ へ向かう直線の右側にある方を $ P' $ としたとき、 $ P' $ の幾何中心（多角形の内部を一様な密度の薄板とみなしたときの重心）の座標を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

$ Q $ 行出力せよ。 $ j $ 行目には、 $ j $ 番目の質問の答えの座標を $ (p_j,q_j) $ としたとき、 $ p_j,q_j $ をこの順に空白区切りで出力せよ。 $ p_j,q_j $ のそれぞれについて、真の解との絶対誤差または相対誤差が $ 10^{-6} $ 以下であれば正解として扱われる。

### Sample Explanation 1 $ 1 $ つ目の質問について、 $ P' $ は $ (1,3),(-3,2),(-1,-2) $ を頂点とする三角形であり、幾何中心は $ (-1,1) $ です。 $ 2 $ つ目の質問について、 $ P' $ は $ (2,-1),(4,1),(1,3),(-3,2) $ を頂点とする四角形であり、幾何中心は $ \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) $ は反時計回りに凸多角形をなす - $ P $ のすべての内角は $ 180 $ 度未満 - $ 1 \leq u_j,v_j \leq N $ - $ u_j \neq v_j $ - $ P $ の周上で頂点 $ u_j $ と頂点 $ v_j $ は隣り合わない - 入力はすべて整数