哈格是一个非常有才华的人。他内心一直有一位艺术家,但他的父亲强迫他学习机械工程。
昨天,他花了所有时间切割一块巨大的木头,试图让它看起来像一只鹅。不管怎样,他的父亲发现他在研究艺术而不是学习机械和其他无聊的学科。他向哈格坦白,他是一个被宠坏的儿子,不关心自己的未来,如果他继续从事艺术,他将削减每月 25 里拉的津贴。
Hag 试图向他的父亲证明木件是力学学科的一个项目。他还告诉他的爸爸,这块木头是一个严格的凸多边形,有 $$$n$$$ 个顶点。
Hag 带来了两个别针,并将多边形的 $$$1$$$-st 和 $$$2$$$-nd 顶点固定在墙上。他的父亲向女巫提出了两种类型的 $$$q$$$ 询问。
- $$$1$$$ $$$f$$$ $$$t$$$:从顶点$$$f$$$拔出一根销钉,等待木质多边形在重力作用下旋转(如果会旋转)并稳定下来。然后将图钉放在顶点$$$t$$$上。
- $$$2$$$ $$$v$$$:回答顶点$$$v$$$的坐标是多少。
请帮助哈格回答他父亲的疑问。
您可以假设形成多边形的木材具有均匀的密度,并且多边形具有正厚度,所有点都相同。在第一种类型的每次查询之后,Hag 的父亲尝试稍微移动多边形并观察它再次稳定下来。
输入
第一行包含两个整数 $$$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$$$ 开头。第一种类型的每个查询都以两个整数 $$$f$$$ 和 $$$t$$$ ($$$1 \le f, t \le n$$$) 继续 - 从中获取引脚的顶点,以及将引脚放置到的顶点,并且多边形完成旋转。保证顶点 $$$f$$$ 包含一个 pin。第二种类型的每个查询都以单个整数 $$$v$$$ ($$$1 \le v \le n$$$) 结尾——Hag 应该告诉他父亲的顶点坐标。
保证至少有一个第二类型的查询。
输出
输出应包含第二种类型的每个查询的答案 - 单独行中的两个数字。如果您的答案的绝对或相对误差不超过 $$$10^{-4}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。如果 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$ 则认为您的答案是正确的
示例
输入 #1
3 4 0 0 2 0 2 2 1 1 2 2 1 2 2 2 3
输出 #1
3.4142135624 -1.4142135624 2.0000000000 0.0000000000 0.5857864376 -1.4142135624
输入 #2
3 2 -1 1 0 0 1 1 1 1 2 2 1
输出 #2
1.0000000000 -1.0000000000
注意
在第一个测试中记下木质多边形的初始和最终状态。
红色三角形是初始状态,绿色三角形是绕 $$$(2,0)$$$ 旋转后的三角形。
在第二个示例中,请注意多边形逆时针或顺时针方向旋转 $$$180$$$ 度(这并不重要),因为 Hag 的父亲确保多边形稳定并且他的儿子不会欺骗他。