Problem G
The walk in DAG

Você está jogando um novo jogo chamando The walk in DAG. Nesse jogo, você joga como um zumbi que precisa andar em um grafo direcionado acíclico para conseguir comida.

No jogo, cada nó tem prioridades diferentes para as arestas saindo dele.

Zumbis são bem burros e só conseguem seguir um conjunto bem simples de instruções.

• ~ X: O zumbi anda $X$ passos no grafo, sempre pegando a aresta de maior prioridade.

• ^ X: O zumbi anda $1$ passo no grafo, pegando a aresta com a $X$-ésima maior prioridade.

As instruções ~  e ^, são o mesmo que ~ $1$ e ^ $1$, respectivamente. Concatenação de instruções válidas também é uma instrução válida.

Você está curioso para saber aonde um zumbi vai parar se começar no nó $s$ e seguir as instruções $t$.

Entrada

A primeira linha da entrada contém um inteiro, $2 \leq N \leq 10^5$, a quantidade de nós no grafo.

As próximas $N$ linhas descrevem as arestas do grafo.

A $i$-ésima linha descreve as arestas do nó $i$ (Nós são números de $1$ até $N$). O primeiro número da linha $1 \leq E_ i < N$ é a quantidade de arestas saindo de $i$. Os próximos $E_ i$ números $1 \leq e_ j \leq N$ indicam uma aresta de $i$ até $e_ j$. Essas arestas são dadas em ordem de prioridade, isso é, a $j$-ésima aresta de $i$ é a aresta com a $j$-ésima maior prioridade. É garantido que $\sum ^{N}_{i=1} E_ i \leq 10^5$.

A próxima linha da entrada contém um número, $1 \leq Q \leq 10^5$, o número de queries que precisam ser respondidas.

As próximas $Q$ linhas descrevem uma query cada.

A $j$-ésima linha tem um inteiro $1 \leq s_ j \leq N$ e uma string $t_ j$. Isso diz que o zumbi deve começar no nó $s_ j$ e seguir as instruções da string $t_ j$. É garantido que $t_ j$ é uma instrução válida e que seguir $t_ j$ começando em $s_ j$ sempre segue um caminho existente no grafo. Também é garantido que $\sum ^{Q}_{j=1} |t_ j| \leq 10^6$.

Saída

A saída deve conter $Q$ linhas. A $i$-ésima linha deve conter um único inteiro $1 \leq x \leq N$, o nó final depois de seguir a $i$-ésima instrução.

4
0
0
2 1 2
1 3
5
3 ^
3 ^2
3 ~
4 ~^2
4 ~2

1
2
1
2
1