题目描述

工厂里有 $n$ 条彼此平行的传送带，编号 $1$ 到 $n$，所有传送带都沿同一方向运输物品。

沿传送带方向依次布置了 $m$ 台机器，编号 $1$ 到 $m$。第 $i$ 台机器连接传送带 $a_i$ 和 $b_i$：若机器正常工作，则物品经过这台机器时会从当前传送带切换到另一条传送带；若机器损坏，则不会发生交换。

需要处理两类在线操作：

• 某台机器的状态翻转：正常变损坏，或损坏变正常；
• 查询一个物品从某条传送带起点放入后，最终会从哪条传送带末端出来。

查询还带有在线加密：当前查询参数会依赖上一条查询的答案，因此必须按顺序处理。

初始时所有机器均正常工作。

输入格式

第一行两个整数 $n,m$，$2\le n,m\le100000$。

接下来 $m$ 行，第 $i$ 行两个整数 $a_i,b_i$，满足 $1\le a_i,b_i\le n$ 且 $a_i\ne b_i$，表示第 $i$ 台机器连接的两条传送带。机器按其在生产线上的先后顺序给出。

随后一行一个整数 $q$，$1\le q\le100000$，表示操作数。

每个操作占一行：

• C k：翻转第 $k$ 台机器的工作状态，$1\le k\le m$；
• Q k：进行一次查询，$1\le k\le n$。

对于查询 Q k，实际放入物品的传送带编号为

$1+((k+d)\bmod n)$，

其中 $d$ 是上一条查询的答案；若这是第一条查询，则 $d=0$。

输出格式

对于每条 Q 操作输出一行，表示物品最终离开时所在的传送带编号。

样例输入

5 5
1 2
2 3
3 1
1 2
1 3
5
Q 1
C 1
Q 2
C 3
Q 3

样例输出

1
4
3