Let's define the majority of a sequence of $k$ elements as the unique value that appears strictly more than $\left \lfloor {\frac{k}{2}} \right \rfloor$ times. If such a value does not exist, then the sequence does not have a majority. For example, the sequence $[1,3,2,3,3]$ has a majority $3$ because it appears $3 > \left \lfloor {\frac{5}{2}} \right \rfloor = 2$ times, but $[1,2,3,4,5]$ and $[1,3,2,3,4]$ do not have a majority.

Skibidus found a tree$^{\text{∗}}$ of $n$ vertices and an array $a$ of length $n$. Vertex $i$ has the value $a_i$ written on it, where $a_i$ is an integer in the range $[1, n]$.

For each $i$ from $1$ to $n$, please determine if there exists a non-trivial simple path$^{\text{†}}$ such that $i$ is the majority of the sequence of integers written on the vertices that form the path.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 5 \cdot 10^5$)  — the number of vertices.

The second line of each test case contains $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le n$)  — the integers written on the vertices.

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$, denoting the two vertices connected by an edge ($1 \le u_i,v_i \le n$, $u_i \neq v_i$).

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output a binary string $s$ of length $n$ on a separate line. $s_i$ should be computed as follows:

• If there is a non-trivial path containing $i$ as the majority, $s_i$ is '1';
• Otherwise, $s_i$ is '0'.

见题面 Input 部分

见题面 Output 部分

In the first test case, there is no non-trivial path with $1$, $2$, or $3$ as a majority, so the binary string outputted is "000".

In the second test case, $1\rightarrow 2\rightarrow 4$ is a non-trivial path with $3$ as a majority.