题目背景

题目描述

有 $n$ 支军队分布在各地，可以看作在一个平面直角坐标系内。他们都受 kid 的统一指挥，kid 共发出 $m$ 条命令。

命令有如下几种：

• 1 p q 表示把每支军队的位置从 $(x_i,y_i)$ 移到 $(x_i+p,y_i+q)$。
• 2 i，表示第 $i$ 支军队的位置对直线 $y=x$ 作轴对称变换（即交换 $x_i$ 与 $y_i$ 的值）。
• 3 i，表示查询第 $i$ 支军队现在所处的位置（即输出此时的 $x_i$ 与 $y_i$）。

请注意 1 与 2 命令的操作对象不同，前者为全体军队，后者为单支军队。

本来 kid 可以直接拿望远镜看的，但是天太黑了，只能拜托你编写一个程序告诉他了。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$ 表示第 $i$ 支军队的初始位置 $(x_i,y_i)=(a_i,b_i)$。

接下来 $m$ 行，每行两到三个整数，表示 kid 发出的一条命令。具体地，对于每条命令，先有一个正整数 $op$ 表示命令类型；

• 如果 $op=1$，那么后面有两个整数 $p,q$，表示把每支军队的位置从 $(x_i,y_i)$ 移到 $(x_i+p,y_i+q)$。
• 如果 $op=2$，那么后面有一个正整数 $i$，表示第 $i$ 支军队的位置对 $y=x$ 做轴对称变换。
• 如果 $op=3$，那么后面有一个正整数 $i$，表示查询第 $i$ 支军队现在所处的位置。

输出格式

对于每次 kid 发出的一条 3 命令，输出一行两个整数 $x_i,y_i$ 表示第 $i$ 支军队现在所处的位置。

3 7
1 2
2 5
6 2
3 2
1 1 4
3 3
2 3
3 1
1 -9 -1
3 3

2 5
7 6
2 6
-3 6

提示

【数据范围】

该题共有 $10$ 个测试点，每个测试点等分。

• 对于 $20\%$ 的数据，$n,m\leqslant 1000$。
• 对于另外 $30\%$ 的数据，保证没有 2 命令。

对于 $100\%$ 的数据，$1\leqslant n\leqslant 10^5$，$1\leqslant m\leqslant 5\times10^5$，$|a_i|,|b_i|,|p|,|q|\leqslant 10^3$，$1\leqslant i\leqslant n$，$op\in\{1,2,3\}$。

【样例解释】