旋转与翻转

题目描述

在二维平面上放置了 $N$ 个棋子。棋子编号为 $1$ 到 $N$，棋子 $i$ 所在的坐标为 $(X_i,Y_i)$。多个棋子可能位于同一坐标。

按顺序执行 $M$ 个操作 $\mathrm{op}_1, \ldots, \mathrm{op}_M$。操作有 $4$ 种，输入格式和操作内容如下：

• 1：将所有棋子移动到以原点为中心顺时针旋转 $90$ 度的位置
• 2：将所有棋子移动到以原点为中心逆时针旋转 $90$ 度的位置
• 3 p：将所有棋子移动到关于直线 $x=p$ 对称的位置
• 4 p：将所有棋子移动到关于直线 $y=p$ 对称的位置

给定 $Q$ 个查询。第 $i$ 个查询给出 $2$ 个整数 $A_i,B_i$，请输出执行完第 $A_i$ 个操作后棋子 $B_i$ 所在的坐标。这里，第 $1$ 个操作之前视为「第 $0$ 个操作之后」。

输入格式

输入按以下格式从标准输入给出：

$N$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$
$M$
$\mathrm{op}_1$
$\vdots$
$\mathrm{op}_M$
$Q$
$A_1$ $B_1$
$\vdots$
$A_Q$ $B_Q$

输出格式

对每个查询输出答案，每行一个，按 $x$ 坐标、$y$ 坐标的顺序用空格分隔。

样例

1
1 2
4
1
3 3
2
4 2
5
0 1
1 1
2 1
3 1
4 1

1 2
2 -1
4 -1
1 4
1 0

最初，唯一的棋子棋子 $1$ 位于 $(1,2)$。通过各操作，棋子 $1$ 的位置按 $(1,2)\to(2,-1)\to(4,-1)\to(1,4)\to(1,0)$ 变化。

2
1000000000 0
0 1000000000
4
3 -1000000000
4 -1000000000
3 1000000000
4 1000000000
2
4 1
4 2

5000000000 4000000000
4000000000 5000000000

数据范围

• 输入均为整数
• $1 \leq N \leq 2\times 10^5$
• $1 \leq M \leq 2\times 10^5$
• $1 \leq Q \leq 2\times 10^5$
• $-10^9 \leq X_i,Y_i \leq 10^9$
• $\mathrm{op}_i$ 符合 $4$ 种操作类型中某一种的输入格式
• 在 3 p 和 4 p 操作中，$-10^9 \leq p \leq 10^9$
• $0 \leq A_i \leq M$
• $1 \leq B_i \leq N$