Problem G
The walk in DAG

You are playing a new game called The walk in DAG. In this game you play as a zombie and need to walk in a directed acyclic graph to get to your food.

In the game, every node has different priorities for it’s outgoing edges.

Zombies are pretty dumb and can only follow a simple set of instructions:

• ~ X: The zombie walks $X$ steps in the graph, always taking the edge with the highest priority.

• ^ X: The zombie walks $1$ step in the graph, taking the edge with the $X$-th highest priority in that node.

There are also instructions ~  and ^, which are the same as ~ $1$ and ^ $1$, respectively. Concatenation of valid instructions are also a valid.

You are curious to know where your zombie ends up if you start at some node $s$ and follow a set of instructions $t$.

Input

The first line of input has one integers, $2 \leq N \leq 10^5$, the number of nodes in the graph.

The next $N$ lines describe the edges of the graph.

The $i$-th line describes the edges of node $i$ (Nodes are numbered from $1$ to $N$). The first number in the line $1 \leq E_ i < N$ is the amount of outgoing edges from that node. The next $E_ i$ numbers $1 \leq e_ j \leq N$ represent an edge from $i$ to $e_ j$. This edges are given in order of priority, that is, $j$-th outgoing edge from $i$ has the $j$-th highest priority. It is guaranteed that $\sum ^{N}_{i=1} E_ i \leq 10^5$.

The next line of input has one integer, $1 \leq Q \leq 10^5$, the number of queries that need to be answered.

The following $Q$ lines describe one query each.

The $j$-th line has one integer $1 \leq s_ j \leq N$ and a string $t_ j$. This tells the zombie to start at node $s_ j$ and follow instructions in string $t_ j$. It is guaranteed that $t_ j$ is a valid instruction and that following string $t_ j$ starting at node $s_ j$ will form a path inside the graph. It’s also guaranteed that $\sum ^{Q}_{j=1} |t_ j| \leq 10^6$.

Output

The output should consist of $Q$ lines. The $i$-th line should have only one integer $1 \leq x \leq N$, the ending node after following the $i$-th set of instructions.

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

1
2
1
2
1