CF975E.Hag's Khashba

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.

哈格是一位非常有天赋的人。他内心一直住着一位艺术家，但他的父亲强迫他学习机械工程。

昨天，他花了整整一天的时间，切割一块巨大的木料，试图把它雕成一只鹅的样子。总之，他父亲发现他并没有在学习机械和其他枯燥的学科，而是在搞艺术。父亲质问他：你是个被宠坏的孩子，根本不在乎自己的未来；如果你继续搞艺术，就将取消你每月25利拉的零花钱。

哈格正试图向父亲证明：这块木料其实是机械学课程的一个项目。他还告诉父亲，这块木料是一个具有 $n$ 个顶点的严格凸多边形。

哈格拿来两枚图钉，将多边形的第 $1$ 个顶点和第 $2$ 个顶点钉在墙上。他父亲向哈格提出了 $q$ 个查询，分为两类：

• 1 f t：从顶点 $f$ 上拔出图钉，等待木制多边形在重力作用下（若会发生转动）旋转并最终稳定下来；然后将图钉钉入顶点 $t$。
• 2 v：回答顶点 $v$ 当前的坐标是什么。

请帮助哈格回答他父亲的这些查询。

你可以假设构成该多边形的木材密度均匀，且多边形在所有位置具有相同的正厚度。每次执行第 $1$ 类查询后，哈格的父亲都会轻微拨动一下多边形，并观察它再次稳定下来。

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.

第一行包含两个整数 $n$ 和 $q$（$3\leq n \leq 10\,000$，$1 \leq q \leq 200000$）—— 分别表示多边形的顶点数和查询次数。

接下来的 $n$ 行描述该木制多边形，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$|x_i|, |y_i|\leq 10^8$）—— 表示多边形第 $i$ 个顶点的坐标。保证该多边形严格凸，且顶点按逆时针顺序给出，所有顶点互不相同。

接下来的 $q$ 行描述各次查询，每行一个查询。每个查询以类型编号 $1$ 或 $2$ 开头。类型 $1$ 的查询随后给出两个整数 $f$ 和 $t$（$1 \le f, t \le n$）—— 分别表示拔出图钉的顶点编号和插入图钉并使多边形完成旋转的顶点编号；保证顶点 $f$ 上当前有图钉。类型 $2$ 的查询随后给出一个整数 $v$（$1 \le v \le n$）—— 表示 Hag 需向他父亲报告其坐标的顶点编号。

保证至少存在一次类型 $2$ 的查询。

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

对于每个第二类查询，输出应包含两个数字，且每个数字占一行。若你的答案的绝对误差或相对误差不超过 $10^{-4}$，则视为正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$ 时，你的答案被视为正确。

In the first test note the initial and the final state of the wooden polygon.

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.

在第一个测试用例中，请注意木制多边形的初始状态与最终状态。

红色三角形为初始状态，绿色三角形为绕点 $(2,0)$ 旋转后的状态。

在第二个样例中，请注意该多边形旋转了 $180$ 度（逆时针或顺时针方向均可，二者等价），因为 Hag 的父亲确保多边形处于稳定状态，且他的儿子不会欺骗他。