Hag is a very talented person. He has always had an artist inside him but his father forced him to study mechanical engineering.
Yesterday he spent all of his time cutting a giant piece of wood trying to make it look like a goose. Anyway, his dad found out that he was doing arts rather than studying mechanics and other boring subjects. He confronted Hag with the fact that he is a spoiled son that does not care about his future, and if he continues to do arts he will cut his 25 Lira monthly allowance.
Hag is trying to prove to his dad that the wooden piece is a project for mechanics subject. He also told his dad that the wooden piece is a **strictly convex** polygon with $n$ vertices.
Hag brought two pins and pinned the polygon with them in the $1$\-st and $2$\-nd vertices to the wall. His dad has $q$ queries to Hag of two types.
* $1$ $f$ $t$: pull a pin from the vertex $f$, wait for the wooden polygon to rotate under the gravity force (if it will rotate) and stabilize. And then put the pin in vertex $t$.
* $2$ $v$: answer what are the coordinates of the vertex $v$.
Please help Hag to answer his father's queries.
You can assume that the wood that forms the polygon has uniform density and the polygon has a positive thickness, same in all points. After every query of the 1-st type Hag's dad tries to move the polygon a bit and watches it stabilize again.
## Input
The first line contains two integers $n$ and $q$ ($3\leq n \leq 10\,000$, $1 \leq q \leq 200000$) — the number of vertices in the polygon and the number of queries.
The next $n$ lines describe the wooden polygon, the $i$\-th line contains two integers $x_i$ and $y_i$ ($|x_i|, |y_i|\leq 10^8$) — the coordinates of the $i$\-th vertex of the polygon. It is guaranteed that polygon is strictly convex and the vertices are given in the counter-clockwise order and all vertices are distinct.
The next $q$ lines describe the queries, one per line. Each query starts with its type $1$ or $2$. Each query of the first type continues with two integers $f$ and $t$ ($1 \le f, t \le n$) — the vertex the pin is taken from, and the vertex the pin is put to and the polygon finishes rotating. It is guaranteed that the vertex $f$ contains a pin. Each query of the second type continues with a single integer $v$ ($1 \le v \le n$) — the vertex the coordinates of which Hag should tell his father.
It is guaranteed that there is at least one query of the second type.
## Output
The output should contain the answer to each query of second type — two numbers in a separate line. Your answer is considered correct, if its absolute or relative error does not exceed $10^{-4}$.
Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$
[samples]
## Note
In the first test note the initial and the final state of the wooden polygon.
<center></center>Red Triangle is the initial state and the green one is the triangle after rotation around $(2,0)$.
In the second sample note that the polygon rotates $180$ degrees counter-clockwise or clockwise direction (it does not matter), because Hag's father makes sure that the polygon is stable and his son does not trick him.
Hag 是一个非常有天赋的人。他内心一直是个艺术家，但他的父亲强迫他学习机械工程。
昨天，他花了整整一天时间切割一块大木头，试图把它做成一只鹅的样子。然而，他的父亲发现他并没有学习机械力学和其他枯燥的科目，而是在搞艺术。父亲当面指责 Hag 是个被宠坏的儿子，不关心自己的未来，如果他继续搞艺术，就会取消他每月 25 Lira 的零花钱。
Hag 试图向父亲证明，这块木头是机械课程的项目。他还告诉父亲，这块木头是一个具有 $n$ 个顶点的*严格凸多边形*。
Hag 拿了两枚钉子，将多边形的第 $1$ 个和第 $2$ 个顶点钉在墙上。他的父亲向他提出了 $q$ 个问题，分为两种类型。
请帮助 Hag 回答他父亲的问题。
你可以假设构成多边形的木材密度均匀，且多边形具有均匀的厚度。在每次第一类查询后，Hag 的父亲都会尝试轻微移动多边形，然后观察它重新稳定。
第一行包含两个整数 $n$ 和 $q$（$3 \leq n \leq 10\,000$，$1 \leq q \leq 200\,000$）—— 分别表示多边形的顶点数和查询次数。
接下来 $n$ 行描述木制多边形，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \leq 10^8$）—— 表示多边形第 $i$ 个顶点的坐标。保证多边形是严格凸的，顶点按逆时针顺序给出，且所有顶点互不相同。
接下来 $q$ 行描述查询，每行一个。每个查询以类型 $1$ 或 $2$ 开头。第一类查询后跟两个整数 $f$ 和 $t$（$1 \leq f, t \leq n$）—— 表示从顶点 $f$ 拔出钉子，并将其插入顶点 $t$，多边形随后停止旋转。保证顶点 $f$ 上有钉子。第二类查询后跟一个整数 $v$（$1 \leq v \leq n$）—— 表示 Hag 需要告诉父亲其坐标的顶点。
保证至少存在一个第二类查询。
对于每个第二类查询，输出一行两个数字。你的答案若满足绝对误差或相对误差不超过 $10^{-4}$，则被视为正确。
形式上，设你的答案为 $a$，标准答案为 $b$，当 $\frac{|a - b|}{\max(1, |b|)} \leq 10^{-4}$ 时，你的答案被认为是正确的。
在第一个测试用例中，展示了木制多边形的初始状态和最终状态。
红色三角形为初始状态，绿色三角形为绕点 $(2, 0)$ 旋转后的状态。
在第二个样例中，注意多边形会旋转 $180$ 度，无论是逆时针还是顺时针方向（无关紧要），因为 Hag 的父亲确保多边形稳定，不会被儿子欺骗。
## Input
第一行包含两个整数 $n$ 和 $q$（$3 \leq n \leq 10\,000$，$1 \leq q \leq 200\,000$）—— 分别表示多边形的顶点数和查询次数。接下来 $n$ 行描述木制多边形，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \leq 10^8$）—— 表示多边形第 $i$ 个顶点的坐标。保证多边形是严格凸的，顶点按逆时针顺序给出，且所有顶点互不相同。接下来 $q$ 行描述查询，每行一个。每个查询以类型 $1$ 或 $2$ 开头。第一类查询后跟两个整数 $f$ 和 $t$（$1 \leq f, t \leq n$）—— 表示从顶点 $f$ 拔出钉子，并将其插入顶点 $t$，多边形随后停止旋转。保证顶点 $f$ 上有钉子。第二类查询后跟一个整数 $v$（$1 \leq v \leq n$）—— 表示 Hag 需要告诉父亲其坐标的顶点。保证至少存在一个第二类查询。
## Output
输出应包含每个第二类查询的答案——每行两个数字。你的答案若满足绝对误差或相对误差不超过 $10^{-4}$，则被视为正确。形式上，设你的答案为 $a$，标准答案为 $b$，当 $\frac{|a - b|}{\max(1, |b|)} \leq 10^{-4}$ 时，你的答案被认为是正确的。
[samples]
## Note
在第一个测试用例中，展示了木制多边形的初始状态和最终状态。红色三角形为初始状态，绿色三角形为绕点 $(2, 0)$ 旋转后的状态。在第二个样例中，注意多边形会旋转 $180$ 度，无论是逆时针还是顺时针方向（无关紧要），因为 Hag 的父亲确保多边形稳定，不会被儿子欺骗。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of vertices of a strictly convex polygon.
Let $ P = (V_1, V_2, \dots, V_n) $ be the sequence of vertices in counter-clockwise order, where $ V_i = (x_i, y_i) \in \mathbb{R}^2 $.
Let $ C = \left( \frac{1}{n} \sum_{i=1}^n x_i, \frac{1}{n} \sum_{i=1}^n y_i \right) $ be the centroid of the polygon’s vertex set (approximation for center of mass under uniform density).
Let $ A = \frac{1}{2} \sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i) $ be the signed area of the polygon, with $ V_{n+1} = V_1 $.
Let $ G = \left( \frac{1}{6A} \sum_{i=1}^n (x_i + x_{i+1})(x_i y_{i+1} - x_{i+1} y_i), \frac{1}{6A} \sum_{i=1}^n (y_i + y_{i+1})(x_i y_{i+1} - x_{i+1} y_i) \right) $ be the **center of mass** of the polygon (uniform density, 2D lamina).
Let $ q \in \mathbb{Z} $ be the number of queries.
Let $ Q = \{ (type_k, \text{params}_k) \mid k \in \{1, \dots, q\} \} $ be the sequence of queries, where:
- If $ type_k = 1 $: $ (f_k, t_k) $, meaning the pin is moved from vertex $ f_k $ to vertex $ t_k $.
- If $ type_k = 2 $: $ (v_k) $, meaning the current coordinates of vertex $ v_k $ must be output.
Let $ R_k \in \mathbb{R}^{2 \times 2} $ be the rotation matrix applied after the $ k $-th type-1 query, and let $ T_k \in \mathbb{R}^2 $ be the translation vector such that the polygon is rigidly transformed to stabilize with a pin at $ t_k $.
Let $ S \subseteq \{1, \dots, n\} $ be the set of pinned vertices. Initially, $ S = \{1, 2\} $. After each type-1 query, $ S $ updates: remove $ f $, add $ t $.
**Constraints**
1. $ 3 \le n \le 10^4 $, $ 1 \le q \le 2 \cdot 10^5 $
2. $ |x_i|, |y_i| \le 10^8 $
3. Polygon is strictly convex, vertices given in counter-clockwise order, all distinct.
4. For each type-1 query: $ f \in S $, $ t \in \{1, \dots, n\} $, $ f \ne t $.
5. At least one type-2 query exists.
**Objective**
After each type-1 query, the polygon rotates rigidly about the new pin $ t $ until it stabilizes under gravity — i.e., the center of mass $ G $ comes to rest **directly below** the pin $ t $ (in the global coordinate system, with gravity in the $ -y $ direction).
Thus, after each type-1 query $ (f, t) $:
- The polygon is rotated about point $ V_t $ by angle $ \theta $ such that the vector $ \vec{V_t G'} $ becomes vertically downward, i.e.,
$$
G' - V_t = (0, -d) \quad \text{for some } d > 0
$$
where $ G' $ is the center of mass in the new orientation.
This rotation is equivalent to:
- Translate the polygon so that $ V_t $ is at origin: $ V_i' = V_i - V_t $
- Rotate the entire polygon by angle $ \phi = \text{atan2}(G_y - V_{t,y}, G_x - V_{t,x}) + \frac{\pi}{2} $
(so that the vector from $ V_t $ to $ G $ becomes aligned with $ (0, -1) $)
- Translate back by $ +V_t $
After the rotation, the new position of any vertex $ V_i $ is:
$$
V_i^{\text{new}} = R(\phi) \cdot (V_i - V_t) + V_t
$$
where $ R(\phi) = \begin{bmatrix} \cos\phi & -\sin\phi \\ \sin\phi & \cos\phi \end{bmatrix} $, and
$$
\phi = \text{atan2}(G_x - V_{t,x}, V_{t,y} - G_y)
$$
For each type-2 query $ v $: output the current coordinates of $ V_v $, computed via cumulative rigid transformations from all prior type-1 queries.
**Note**: The center of mass $ G $ is fixed relative to the polygon (rigid body). Only the orientation changes due to rotation about the pin. Thus, we can precompute $ G $ once, and for each type-1 query, compute the rotation angle needed to align $ \vec{V_t G} $ vertically downward, then apply this rotation to all vertices.
We maintain the current position of each vertex $ V_i $, and update them after each type-1 query.
**Algorithm Summary**
- Precompute $ G $, the center of mass of the polygon.
- Initialize current vertex positions $ V_i^{(0)} = (x_i, y_i) $.
- For each query:
- Type 1 ($ f, t $):
1. Compute vector $ \vec{d} = G - V_t^{(current)} $
2. Compute rotation angle $ \phi = \text{atan2}(d_x, -d_y) $ // rotates $ \vec{d} $ to $ (0, -1) $
3. Apply rotation $ R(\phi) $ about point $ V_t^{(current)} $ to all vertices:
$$
V_i^{\text{new}} = R(\phi) \cdot (V_i - V_t) + V_t
$$
- Type 2 ($ v $): output $ V_v^{(current)} $
**Output**
For each type-2 query, output two real numbers: $ x_v, y_v $, with absolute or relative error $ \le 10^{-4} $.