注意：本题使用加密的输入格式以强制进行在线查询（强制在线）。请仔细阅读输入格式部分以获取更多细节。

这只是金克丝（Jinx）基地里普通的一天。不知怎么的，她那成千上万只猴子（别问为什么）中的一些溜进了她的镜子迷宫（也别问为什么）。而现在——就在现在！——她找不到她心爱的电击枪（Zapper gun）了（说真的，别问）。会不会是某只猴子拿走了它？不——绝无可能。当然。除非……不，绝不可能。……对吧？好吧，以防万一，金克丝想知道：如果真的有一只猴子拿了电击枪并在迷宫里扣动了扳机——谁会被电到？你能帮她算出来吗？（动作要快——在猴子们产生任何想法之前！）

金克丝的镜子迷宫具有以下约束：

• 所有猴子和镜子都精确地位于网格点上。
• 所有镜子都与网格轴呈 $45^\circ$ 角；每面镜子可以表示为 / 或 \，且镜子的双面都是反光的。
• 电击枪只能平行于网格轴发射。

给你猴子和镜子的初始状态。你需要回答以下类型的查询：

• 1 i x y：猴子 $i$ 移动到坐标 $(x, y)$。保证在此查询期间，当前 $(x, y)$ 处没有猴子或镜子。
• 2 x y c：根据 $c$ 切换 $(x, y)$ 处的镜子。如果 $c$ 等于 / 或 \，则在 $(x, y)$ 处放置一面对应 $c$ 的镜子，替换当前位于 $(x, y)$ 处的任何镜子（如果存在）。如果 $c$ 等于 .（英文句号），则移除 $(x, y)$ 处的镜子且不进行替换。保证当 $c$ 等于 . 时，$(x, y)$ 处存在一面镜子。保证无论 $c$ 为何值，$(x, y)$ 处都没有猴子。

• 3 i d：猴子 $i$ 朝方向 $d$ 发射电击枪：

  • 如果 $d$ 等于 N，猴子向北（$y$ 轴正方向）发射电击枪。
  • 如果 $d$ 等于 E，猴子向东（$x$ 轴正方向）发射电击枪。
  • 如果 $d$ 等于 S，猴子向南（$y$ 轴负方向）发射电击枪。
  • 如果 $d$ 等于 W，猴子向西（$x$ 轴负方向）发射电击枪。

电击枪的光束会在镜子上反射，直到击中一只猴子或离开网格。如果它会击中一只猴子，输出该查询中被击中猴子的编号（索引）。否则，该查询输出 -1。

你能想出如何快速拯救电击枪吗？……哦，还有猴子们。

输入格式

第一行包含三个整数 $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^4$)：分别表示猴子的数量、初始镜子的数量和查询的数量。

接下来有若干行：

• 紧接着的 $N$ 行，每行包含一对整数 $(x_i, y_i)$ ($0 \le x_i, y_i \le 10^6$)，表示第 $i$ 只猴子的位置。
• 紧接着的 $M$ 行，每行格式为 $(x_j, y_j, c)$。这里 $x_j$ 和 $y_j$ 是整数 ($0 \le x_j, y_j \le 10^6$)，表示镜子的位置，$c$ 是 / 或 \，表示镜子的类型。

• 紧接着的 $Q$ 行，采用上述查询格式，其中：

  • 对于所有索引 $i$，$1 \le i \le N$
  • 对于所有坐标 $x$ 和 $y$，$0 \le x, y \le 10^6$

保证猴子和镜子的初始放置不包含重复的坐标。保证没有任何两只猴子会同时占据同一个方格。保证对于所有类型 1 的查询，目的地都是空的。保证对于所有类型 2 的查询，目标方格不包含猴子（但在第二种类型的查询中，一面镜子可能会被另一面镜子替换）。

为了强制在线查询，$x$ 坐标和 $y$ 坐标将按以下格式加密。令 $s_i$ 为第 $i$ 次查询之前，所有类型 3 查询的正确答案之和模质数 $10^6 + 3$ 的值。然后，对于任何类型 1 或 2 的查询，将给出加密后的坐标 $x'_i \equiv (x_i - s_i) \pmod{10^6 + 3}$ 和 $y'_i \equiv (y_i - s_i) \pmod{10^6 + 3}$（$0 \le x'_i, y'_i < 10^6 + 3$），而不是实际的 $x_i, y_i$。如果尚未发生类型 3 的查询，则 $s_i$ 为 $0$。

输出格式

对于每个类型 3 的查询，在单独的一行中输出该查询的结果。保证至少会有一个此类查询。

样例

输入样例 1

3 1 9
2 1
2 0
0 2
2 2 \
3 1 N
3 2 N
3 3 E
2 1000000 1000000 /
3 1 N
3 2 N
2 1000000 1000000 \
3 1 N
3 2 N

输出样例 1

3
1
1
-1
1
3
1

输入样例 2

2 4 17
2 2
3 2
1 1 \
1 3 /
5 1 /
5 3 \
3 1 E
3 1 W
1 1 1 0
3 1 E
3 1 W
1 2 0 0
3 1 E
3 2 W
1 1 999998 999999
3 2 E
3 2 W
1 1 999996 999999
3 2 W
2 999994 999996 \
3 2 W
3 2 E
3 1 S

输出样例 2

2
-1
1
1
2
1
1
1
2
1
-1
2

说明

为了方便起见，下面给出了未加密的样例输入。您的代码不会在未加密的输入上进行测试。

未加密样例输入 1

3 1 9
2 1
2 0
0 2
2 2 \
3 1 N
3 2 N
3 3 E
2 2 2 /
3 1 N
3 2 N
2 2 2 \
3 1 N
3 2 N

未加密样例输入 2

2 4 17
2 2
3 2
1 1 \
1 3 /
5 1 /
5 3 \
3 1 E
3 1 W
1 1 2 1
3 1 E
3 1 W
1 2 3 3
3 1 E
3 2 W
1 1 1 2
3 2 E
3 2 W
1 1 1 4
3 2 W
2 1 3 \
3 2 W
3 2 E
3 1 S