#3906. Trie

题目描述


输入格式

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.

输出格式

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

样例

样例输入

1  

6  

1 a  

1 b  

1 c  

3 a  

3 b  

5  

1 2 3 4  

2 2 5 6  

1 2 2 3  

2 2 4 5  

2 1 6

样例输出

2  

3  

4  

数据范围与提示