Alphonse 正在构建一棵字母树，并在此过程中进行一些探险。

字母树是一棵无根树，包含 $N$ 个节点（编号从 $1$ 到 $N$）和 $N-1$ 条边。

初始时，第 $i$ 条边连接节点 $A_i$ 和 $B_i$，且双向连通，边上标记有大写字母 $C_i$。连接同一个节点的任意两条边所标记的字母均不相同。

Alphonse 有 $Q$ 个事件需要处理，第 $i$ 个事件属于以下两种类型之一：

• $1$ $U_i$ $L_i$：通过一条标记为大写字母 $L_i$ 的新边将一个新节点连接到节点 $U_i$，从而向树中添加一个新节点。新添加的节点编号从 $N+1$ 开始，按添加顺序递增。
• $2$ $U_i$ $K_i$ $S_i$：输出 Alphonse 在以下旅程中最终到达的节点：
  • 从节点 $U_i$ 开始旅程。
  • 在旅程中重复遍历之前未遍历过的边。如果当前节点有多条未遍历过的边，他会选择标记字母在字符串 $S_i$ 中出现位置最靠前的那条边。当当前节点没有更多未遍历过的边，或者旅程中已经遍历了 $K_i$ 条边时，旅程结束。

请帮助 Alphonse 确定每次旅程的终点。

数据范围

• $1\le T \le 20$
• $2\le N \le 300,000$
• $1\le Q \le 300,000$
• $1\le A_i, B_i \le N$
• $A_i \not = B_i$
• $C_i, L_i, S_{i,j} \in \{'A', \cdots , 'Z'\}$

• $1\le U_i,K_i \le 600,000$

• 所有测试用例中 $N$ 的总和不超过 $1,100,000$。

• 所有测试用例中 $Q$ 的总和不超过 $1,100,000$。

对于每个事件，保证：

• $U_i$ 在事件发生时是树中的有效节点。
• $L_i$ 与事件发生时连接到 $U_i$ 的所有现有边的标签均不同。
• $S_i$ 中的字母互不相同，且包含了事件发生时树中所有边标签的超集。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例，第一行包含一个整数 $N$。接下来 $N-1$ 行，第 $i$ 行包含空格分隔的整数 $A_i$ 和 $B_i$，以及一个空格和字符 $C_i$。随后一行包含整数 $Q$。接下来 $Q$ 行，每行描述一个事件，格式为 $1$ $U_i$ $L_i$ 或 $2$ $U_i$ $K_i$ $S_i$。

输出格式

对于第 $i$ 个测试用例，输出一行 "Case #i: "，后跟空格分隔的整数，即所有类型为 2 的事件的答案。

说明

第一个样例的字母树如上图所示，旅程结果如下：

• 事件 $1$ 遍历 $1 \stackrel{\texttt{M}}{\longrightarrow} 2 \stackrel{\texttt{E}}{\longrightarrow} 6$（在节点 $6$ 没有更多边后结束）
• 事件 $2$ 遍历 $3 \stackrel{\texttt{E}}{\longrightarrow} 1 \stackrel{\texttt{T}}{\longrightarrow} 4 \stackrel{\texttt{A}}{\longrightarrow} 9$（在遍历 $K_2=3$ 步后结束）
• 事件 $3$ 遍历 $9 \stackrel{\texttt{A}}{\longrightarrow} 4 \stackrel{\texttt{T}}{\longrightarrow} 1 \stackrel{\texttt{M}}{\longrightarrow} 2$（在遍历 $K_3 =3$ 步后结束）
• 事件 $4$ 遍历 $8 \stackrel{\texttt{M}}{\longrightarrow} 3 \stackrel{\texttt{E}}{\longrightarrow} 1 \stackrel{\texttt{T}}{\longrightarrow} 4 \stackrel{\texttt{A}}{\longrightarrow} 9$（在节点 $9$ 没有更多边后结束）
• 事件 $6$ 遍历 $8 \stackrel{\texttt{T}}{\longrightarrow} 10$（在节点 $10$ 没有更多边后结束）

第二个和第三个样例的字母树如下图所示。

第二个样例中，旅程如下：

• 事件 $1$ 遍历 $1 \stackrel{\texttt{P}}{\longrightarrow} 5 \stackrel{\texttt{C}}{\longrightarrow} 2$（在遍历 $K_1 = 2$ 步后结束）
• 事件 $2$ 遍历 $4 \stackrel{\texttt{P}}{\longrightarrow} 2 \stackrel{\texttt{C}}{\longrightarrow} 5 \stackrel{\texttt{P}}{\longrightarrow} 1$（在遍历 $K_2 = 3$ 步后结束）
• 事件 $4$ 遍历 $4 \stackrel{\texttt{P}}{\longrightarrow} 2 \stackrel{\texttt{C}}{\longrightarrow} 5 \stackrel{\texttt{U}}{\longrightarrow} 6$（在遍历 $K_4 = 3$ 步后结束）
• 事件 $5$ 遍历 $3 \stackrel{\texttt{U}}{\longrightarrow} 2 \stackrel{\texttt{P}}{\longrightarrow} 4$（在节点 $4$ 没有更多边后结束）

第三个样例中，旅程如下：

• 事件 $1$ 遍历 $3 \stackrel{\texttt{C}}{\longrightarrow} 2 \stackrel{\texttt{A}}{\longrightarrow} 1$（在遍历 $K_1 = 2$ 步后结束）
• 事件 $2$ 遍历 $4 \stackrel{\texttt{E}}{\longrightarrow} 2 \stackrel{\texttt{A}}{\longrightarrow} 1$（在遍历 $K_2 = 2$ 步后结束）
• 事件 $3$ 遍历 $1 \stackrel{\texttt{A}}{\longrightarrow} 2$（在遍历 $K_3 = 1$ 步后结束）

样例

输入 1

3
9
1 2 M
1 3 E
1 4 T
4 9 A
2 5 T
2 6 E
3 7 A
3 8 M
6
2 1 3 META
2 3 3 TEAM
2 9 3 MATE
2 8 8 TEAM
1 8 T
2 8 8 TEAM
5
1 5 P
5 2 C
2 3 U
4 2 P
5
2 1 2 CPU
2 4 3 CUP
1 5 U
2 4 3 CUP
2 3 4 PUCK
4
2 1 A
2 3 C
4 2 E
3
2 3 2 HACKER
2 4 2 REACH
2 1 1 OCEAN

输出 1

Case #1: 6 9 2 9 10
Case #2: 2 1 6 4
Case #3: 1 1 2