골드버그 기계

루베는 새로 만든 정체를 알 수 없는 장치를 시험하고 있습니다. 이 기계에는 1번부터 $n$번까지 번호가 붙은 노드 $n$개가 있고, 각 노드는 구슬을 하나씩 담을 수 있습니다. 노드들은 $n-1$개의 트랙으로 이어져 있습니다. 트랙을 따라가면 어느 노드에서든 다른 모든 노드에 갈 수 있으므로, 트랙은 무방향 트리를 이룹니다.

각 노드에 인접한 트랙에는 순서가 정해져 있습니다. 노드 $v$에 인접한 트랙이 $k_v$개라면 그 순서를 $e_{v,0}, \ldots, e_{v,k_v-1}$로 씁니다. 각 노드에는 활성 트랙이 하나 선택되어 있습니다. $t_v \in \{0, \ldots, k_v-1\}$는 트랙 $e_{v,t_v}$가 노드 $v$의 활성 트랙임을 뜻합니다.

기계는 다음과 같이 작동합니다. 먼저 구슬을 노드 1에 놓습니다. 그다음 한 단계 이상이 진행되며, 각 단계는 다음과 같습니다.

• 구슬이 노드 $v$에 있으면, 활성 트랙 $e_{v,t_v}$의 반대쪽 끝 노드로 이동합니다.
• 구슬이 옮겨 간 뒤, 단계 시작 시 구슬이 있던 노드는 활성 트랙을 순환 순서상 다음 트랙으로 바꿉니다. 즉 $t_v$는 $(t_v+1) \bmod k_v$가 됩니다.

루베는 다음 두 종류의 질의를 처리하려고 합니다.

• 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$단계를 진행한 뒤 구슬이 있는 노드의 번호를 구합니다. 이 질의는 이후 질의의 시작 설정을 바꾸지 않습니다.

루베는 장치를 만지작거리느라 바쁘니, 빠르게 답해 주세요.

첫 줄에 노드 수 $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}, \ldots, u_{i,k_i-1}$이 주어집니다. 이는 노드 $i$에 인접한 트랙이 $k_i$개이고, 트랙 $e_{i,j}$가 $i$에서 $u_{i,j}$로 이어지며, 트랙 $e_{i,t_i}$가 현재 노드 $i$의 활성 트랙이라는 뜻입니다. 단, $u_{i,j} \ne i$입니다.

주어진 트랙은 무방향 트리를 이룹니다.

• 서로 다른 두 노드 $u$, $v$에 대해, $u$가 $v$에 인접한 트랙의 끝점이면 $v$도 $u$에 인접한 트랙의 끝점입니다.
• 서로 다른 트랙은 $n-1$개이며, $\sum k_i = 2(n-1)$입니다.
• 어떤 노드에서든 트랙을 따라 다른 모든 노드에 갈 수 있습니다.

다음 줄에는 질의 수 $q$($1 \le q \le 10^5$)가 주어집니다. 이어지는 $q$개 줄에는 위에서 설명한 C v t 또는 Q x 형식의 질의가 한 줄에 하나씩 주어집니다.

각 Q x 질의에 대해, 주어진 순서대로 답을 한 줄에 하나씩 출력합니다.

주어진 입력에서 구슬이 이동하는 경로는 다음과 같습니다.

1 → 2 → 1 → 3 → 1 → 2 → 4 → 2 → 5 → 2 → 1

1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 1 → 2 → 4

1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 7 → 3 → 1