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 \gt \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.

$$$^{\text{∗}}$$$A tree is a connected graph without cycles.

$$$^{\text{†}}$$$A sequence of vertices $$$v_1, v_2, ..., v_m$$$ ($$$m \geq 2$$$) forms a non-trivial simple path if $$$v_i$$$ and $$$v_{i+1}$$$ are connected by an edge for all $$$1 \leq i \leq m - 1$$$ and all $$$v_i$$$ are pairwise distinct. Note that the path must consist of at least $$$2$$$ vertices.

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'.

Note

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.

Skibidus and Slay

Examples