题目描述

给定一个大小为 $N \times N$ 的方格表。它的某些格子被染成黑色，其余格子为白色。

这张表画在一张透明纸上，因此可以进行如下变换：

• 向右旋转 $90^\circ$；
• 向左旋转 $90^\circ$；
• 旋转 $180^\circ$；
• 竖直翻转；
• 水平翻转。

这 $5$ 种变换分别用字母表示为：

• R：向右旋转 $90^\circ$
• L：向左旋转 $90^\circ$
• Q：旋转 $180^\circ$
• V：竖直翻转
• H：水平翻转

展示初始方格表以及五种变换 R / L / Q / V / H 对应的效果。

我们有两类操作：

1. 指定一种变换，即上述字母之一 R、L、Q、V、H；
2. R S：给出表中的一行一列编号。如果当前状态下该位置的格子是白色，就把它染成黑色；如果是黑色，就把它染成白色。

整个正方形的坐标系从左上角开始，也就是说，最上方最左侧的格子坐标为 $R=1$、$S=1$。

给定 $M$ 个操作。请编写程序 oper，输出最终状态中“最靠上”的 $K$ 个黑色格子的坐标。

这里“最靠上”的含义是：在所有操作完成后，把所有黑色格子按以下顺序排序：

1. 先按行号升序；
2. 若行号相同，再按列号升序。

你需要输出排序后前 $K$ 个黑色格子的坐标。

输入格式

第一行包含三个正整数 $N$、$T$、$M$，分别表示：

• 方格表的大小；
• 初始时黑色格子的数量；
• 操作数。

接下来 $T$ 行，每行两个正整数 $R$、$S$，表示一个初始为黑色的格子的坐标。

接下来 $M$ 行描述操作。每行都以数字 1 或 2 开头，表示操作类型：

• 若为类型 1，则后面跟一个空格和一个字母 R、L、Q、V、H 之一；
• 若为类型 2，则后面跟两个整数 $R$、$S$，表示要变色的格子坐标。

最后一行是整数 $K$，表示需要输出多少个格子的坐标。

输出格式

输出 $K$ 行，每行两个整数，分别表示一个黑色格子的行号与列号。

输出顺序应与题目中定义的排序顺序一致。

数据范围

$2 \le N, T, M \le 100000$。
$K > 0$，且 $K$ 不超过所有操作结束后黑色格子的数量。

样例

输入

3 3 6
1 1
3 2
3 3
1 R
1 H
2 2 1
1 V
2 1 3
1 H
2

输出

2 1
2 3

样例说明

原题样例中的两条文字说明为：

• 格子 $(2,1)$ 是白色，因此把它染成黑色；
• 格子 $(1,3)$ 是黑色，因此把它染成白色。

子任务

• 子任务 1（3 个测试）：$2 \le N, T, M \le 100$，类型 2 的操作数不超过 $5$。
• 子任务 2（10 个测试）：$2 \le N, T, M \le 10000$，类型 2 的操作数不超过 $100$；并且同一测试中，类型 1 的操作只会来自集合 ${R, L, Q}$ 或集合 ${H, V}$ 之一。
• 子任务 3（10 个测试）：无额外限制。