tree

Problem Description

Given a rooted tree(node 1 is the root) with $n$ nodes. The $i^{th}$node has a positive value $v_i$ at beginning. We define the universal set $S$ includes all nodes. There are two types of Memphis's operation. First, Memphis may change the value of one node. It's the first type operation:

What's more, Memphis wants to know what's the maxinum of $v_u\otimes v_t(t\in path(u,root),\otimes~~means~~xor)$ . It's the second type operation:

Input

This problem has multi test cases(no more than $3$). The first line contains a single integer $T$, which denotes the number of test cases. For each test case,the first line contains two non-negative integer $n,m(1\leq n,m\leq 100000)$ - the number of nodes and operations. The second line contains $n-1$ non-negative integer $f_2\sim f_n(f_i < i)$ - the father of $i^{th}$node. The third line contains $n$ non-negative integer $v_1\sim v_n(0\leq v_i \leq 10^9)$ - the value of nodes at beginning. Follow $m$ lines describe each operation.

Output

For each test cases,for each second operation print a non-negative integer.

Sample Input

1
10 10
1 1 2 2 3 1 2 3 5
23512 460943 835901 491571 399045 97756 413210 800843 283274 106134
0 7 369164
0 7 296167
0 6 488033
0 7 187367
0 9 734984
1 6
0 5 329287
1 5
0 7 798656
1 10

Sample Output

766812
351647
431641

Author

SXYZ

Source

2015 Multi-University Training Contest 8