Tree

Problem Description

Alice and Bob are playing with a magic tree This magic tree has n nodes,with n−1 magic paths connecting them into a connected block. Node 1 is at the top of the magic tree (layer 0). Node i is at the kth layer, where k is the distance from the node i to the node 1. Alice and Bob give a mana value on each node. If a magic stone falls on node i, it will be sent up to the k layer and appear on the kth ancestor node of the i layer(k is the mana value of node i). This node will continue to send up it, and so on. If the layer of node i is less than k, this stone will be sent out of the magic tree. Alice is curious, she will modify the magic value of a node, and ask Bob: If you drop a magic stone on the node x, how many times does it take to transfer it out of the magic tree?

Input

Input contains multiple tests The first line contains one integer T(T≤4), indicating the number of test cases. The following lines describe all the test cases For each test case: The first line contains an integer n(n≤100000), indicating the size of the magic tree. The second line has n−1 numbers, and the ith number represents the father of the node i+1. The third row has n numbers, and the ith number represents the initial mana ai(ai≤n) value of each node. In the fourth line, a number m(m≤100000) represents the number of operations. The next m lines, one operation per line. First a number op(1≤op≤2) represents the type of operation. If op1, a number x will be read immediately, indicating that a magic stone is thrown to the node x. If op2, it will immediately read in two numbers x and new_a, indicating that the magic value of node x is modified to new_a(new_a≤n).

Output

For each query with op==1, output the answer

Sample Input

1
4
1 2 3
1 1 1 1
3
1 4
2 3 2
1 4

Sample Output

4
3

Hint

For the first query: 4->3->2->1->out For the second query:4->3->1->out

Source

2018 Multi-University Training Contest 7