Description

Input

The first line contains an integer T (T ≤ 5), denoting the number of the test cases.For each test case, the first line contains an integer n(1 ≤ n ≤ 105).From the second to the n-th line, this n - 1 lines describe Bob' s Trie. The i-th line contains an integer u(u < i), and a lowercase letter c, which means that the father of node i is node u and the character on that edge is c. We ensure that for each node i, letters on edges connecting i and its children are all different.The next line contains an integer m(m ≤ 105), which means there are m operations.The next m lines describe all operations. In each line, the first integer indicates the type of this operation. 1 means Bob will add a new trait and 2 means Bob is asking you a question. The second integer k is the size of set P , and the next k integers are the elements of P. We ensure that these k integers are different, and they are all between 1 and n. The total size of the m sets will not be larger than 5*10^5.

Output

For each test case, output the answer for each query operation, one answer in a line.

Sample Input

Sample Output

Hint

Source