UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3906. Trie

统计 下载数据

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

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

Sample Output

2
3
4

Hint


Source

2014 Asia AnShan Regional Contest