You are given a rooted tree with vertices. The root of the tree is vertex .
Each vertex has a value a_i, which is either or .
For each size (1 \le k \le n), determine which xor values can be obtained by choosing a set of vertices that satisfies the following conditions:
|S| = k;
if vertex belongs to the set , then all vertices in the subtree of vertex also belong to .
The value of a set is defined as the xor of the values of all vertices in this set: \bigoplus_{v \in S} a_v.
The subtree of vertex is the set of all vertices such that vertex lies on the simple path from the root to vertex .
The xor operation for bits is defined as follows: 0 \oplus 0 = 0, 0 \oplus 1 = 1, 1 \oplus 0 = 1, 1 \oplus 1 = 0.
The child of vertex is a vertex whose parent is .
The first line contains one integer (1 \le t \le 1000) — the number of test cases.
Each test case consists of three lines.
The first line of each test case contains one integer (2 \le n \le 4 \cdot 10^5) — the number of vertices in the tree.
The second line contains integers a_1, a_2, \ldots, a_n (a_i \in \{0, 1\}) — the values of the vertices.
The third line contains n-1 integers p_2, p_3, \ldots, p_n (1 \le p_i < i), where p_i is the parent of vertex .
It is guaranteed that the sum of over all test cases does not exceed 4 \cdot 10^5.
For each test case, output one line with integers ans_1, ans_2, \ldots, ans_n.
For each :
ans_k = 0, if among all valid sets of size only xor can be obtained;
ans_k = 1, if among all valid sets of size only xor can be obtained;
ans_k = 2, if among all valid sets of size both xor and xor can be obtained.
Example 1
This is what the trees in the first and second test cases look like, respectively.
Consider the first test case.
For k = 1, both xor values can be obtained. For example, the set S = \{5\} is valid and has xor . And the set S = \{3\} is also valid and has xor . Therefore, ans_1 = 2.
For k = 3, both xor values can also be obtained. For example, the set S = \{2, 3, 5\} is valid because together with vertex all vertices in its subtree are chosen. Its xor is a_2 \oplus a_3 \oplus a_5 = 0 \oplus 1 \oplus 0 = 1. And the set S = \{3, 4, 5\} is also valid because together with vertex all vertices in its subtree are chosen. Its xor is a_3 \oplus a_4 \oplus a_5 = 1 \oplus 1 \oplus 0 = 0. Therefore, ans_3 = 2.
Thus, the answer for the first test case is .
Consider the second test case.
In this test case, both xor values can be obtained only for k = 6.
For example, the set S = \{3, 4, 6, 7, 8, 9\} is valid. Its xor is a_3 \oplus a_4 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 = 0 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 1.
And the set S = \{4, 5, 6, 7, 8, 9\} is also valid. Its xor is a_4 \oplus a_5 \oplus a_6 \oplus a_7 \oplus a_8 \oplus a_9 = 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 0. Therefore, ans_6 = 2.
Thus, the answer for the second test case is 1\ 0\ 1\ 0\ 1\ 2\ 0\ 0\ 0.
A leaf is a vertex that has no children.
A bamboo is a tree in which every vertex has at most one child.
( points): \sum n \le 20;
( points): p_i=1;
( points): \sum n^3 \le 10^8;
( points): \sum n^2 \le 10^8;
( points): the total number of leaves over all test cases does not exceed ;
( points): after removing vertex , each component is a bamboo, and there are at most two such components;
( points): after removing vertex , each component is a bamboo;
( points): all trees are full binary trees, that is, n = 2^q - 1 for some integer , and for every vertex i > 1 we have p_i = \left\lfloor \frac{i}{2} \right\rfloor;
( points): n \le 2 \cdot 10^5 for each test case;
( points): no additional constraints.