E - 旋转和翻转

分数：500分

问题描述

在一个二维平面上有N个小块。第i个小块的坐标为$(X_i, Y_i)$。可能会有多个小块位于相同的坐标上。

我们将依次进行M个操作，$\mathrm{op}_1,\ldots,\mathrm{op}_M$。操作共有四种，具体格式如下：

• 1：每个小块关于原点顺时针旋转90度；
• 2：每个小块关于原点逆时针旋转90度；
• 3 p：每个小块关于以x=p为轴的直线对称；
• 4 p：每个小块关于以y=p为轴的直线对称。

给定Q个查询。在第i个查询中，给出两个整数$A_i$和$B_i$，输出第$A_i$次操作后第$B_i$个小块的坐标。这里，第一次操作之前被认为是“第0次操作”之后的时刻。

约束条件

• 输入中的所有值均为整数。
• $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$ 符合四种操作中的一种格式。
• 对于形如3 p或4 p的操作，$-10^9 \leq p \leq 10^9$。
• $0 \leq A_i \leq M$
• $1 \leq B_i \leq N$

输入

从标准输入读入，输入格式如下：

$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,2)\rightarrow(2,-1)\rightarrow(4,-1)\rightarrow(1,4)\rightarrow(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