Rube 建造了一个全新的晦涩装置，现在正在对其进行测试。该机器有 $n$ 个编号从 $1$ 到 $n$ 的节点，可以容纳一颗弹珠，并有 $n-1$ 条连接节点的轨道。从任意节点出发，沿着轨道都可以到达其他任何节点，也就是说，这些轨道构成了一棵无向树。

对于每个节点，与其相邻的轨道都是有序的：如果节点 $v$ 有 $k_v$ 条相邻轨道，我们将这些轨道记为 $e_{v,0}, \dots, e_{v,k_v-1}$。此外，每个节点都选定了一条活跃的相邻轨道：我们用 $t_v \in \{0, \dots, k_v-1\}$ 来表示节点 $v$ 的活跃轨道是 $e_{v,t_v}$。

该机器的运行方式如下：首先，将一颗弹珠放置在节点 $1$。然后，进行一步或多步操作。每一步的操作过程如下： 如果弹珠当前位于节点 $v$，它会移动到轨道 $e_{v,t_v}$（节点 $v$ 当前的活跃轨道）的另一个端点。 在弹珠移动到新节点后，$t_v$ 变为 $(t_v + 1) \pmod{k_v}$（也就是说，在步骤开始时包含弹珠的节点，其活跃轨道会变为循环顺序中的下一条）。

Rube 希望你处理两种类型的查询： “C $v$ $t$” ($1 \le v \le n, 0 \le t \le k_v-1$)：将 $t_v$ 设置为 $t$； “Q $x$” ($1 \le x \le 10^{18}$)：确定从当前配置出发，从节点 $1$ 开始经过恰好 $x$ 步后，弹珠所在的节点编号。注意，此查询不会影响后续查询的初始配置。

Rube 忙于摆弄他的设备，所以他希望你能快速回答！

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)：机器中的节点数。 接下来的 $n$ 行描述了轨道。第 $i$ 行包含两个整数 $k_i$ 和 $t_i$ ($0 \le t_i \le k_i-1$)，随后是 $k_i$ 个不同的整数 $u_{i,0}, \dots, u_{i,k_i-1}$ ($u_{i,j} \neq i$)。这表示： 节点 $i$ 有 $k_i$ 条相邻轨道； 对于任意 $j \in \{0, \dots, k_i-1\}$，轨道 $e_{i,j}$ 从 $i$ 通向 $u_{i,j}$； * 轨道 $e_{i,t_i}$ 当前是节点 $i$ 的活跃轨道。

保证所描述的轨道构成一棵无向树，即： 对于任意一对不同的节点 $(u, v)$，节点 $u$ 是与 $v$ 相邻的轨道的端点，当且仅当 $v$ 是与 $u$ 相邻的轨道的端点； 共有 $n-1$ 条不同的无向轨道，即 $\sum_{i=1}^n k_i = 2(n-1)$； * 从任意节点出发，沿着轨道都可以到达其他任何节点。

接下来一行包含一个整数 $q$ ($1 \le q \le 10^5$)：查询次数。 接下来的 $q$ 行按上述格式描述查询，每行一个。

输出格式

按询问顺序输出所有 “Q $x$” 查询的答案，每行一个。

样例

输入 1

7
2 0 2 3
3 0 1 4 5
3 0 1 6 7
1 0 2
1 0 2
1 0 3
1 0 3
5
Q 10
C 2 1
Q 10
C 3 2
Q 10

输出 1

1
4
1

说明

以下是样例中弹珠的路径： 1. $1 \to 2 \to 1 \to 3 \to 1 \to 2 \to 4 \to 2 \to 5 \to 2 \to 1$ 2. $1 \to 2 \to 4 \to 2 \to 5 \to 2 \to 1 \to 3 \to 1 \to 2 \to 4$ 3. $1 \to 2 \to 4 \to 2 \to 5 \to 2 \to 1 \to 3 \to 7 \to 3 \to 1$