Of course, a problem with the letter D is sponsored by Declan Akaba.

You are given a simple, connected, undirected graph with $n$ vertices and $m$ edges. The graph contains no self-loops or multiple edges. You are also given a multiset $A$ consisting of $\ell$ elements: $$ A = \{A_1, A_2, \ldots, A_\ell\} $$

Starting from vertex $1$, you may perform the following move any number of times, as long as the multiset $A$ is not empty:

• Select an element $k \in A$ and remove it from the multiset . You must remove exactly one occurrence of $k$ from $A$.
• Traverse any walk$^{\text{∗}}$ of exactly $k$ edges to reach some vertex (possibly the same one you started from).

For each $i$ ($1 \le i \le n$), determine whether there exists a sequence of such moves that starts at vertex $1$ and ends at vertex $i$, using the original multiset $A$.

Note that the check for each vertex $i$ is independent — you restart from vertex $1$ and use the original multiset $A$ for each case.

$^{\text{∗}}$A walk of length $k$ is a sequence of vertices $v_0, v_1, \ldots, v_{k - 1}, v_k$ such that each consecutive pair of vertices $(v_i, v_{i + 1})$ is connected by an edge in the graph. The sequence may include repeated 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 three integers $n$, $m$, and $\ell$ ($2 \leq n \leq 2 \cdot 10^5$, $n-1 \leq m \leq 4 \cdot 10^5$, $1 \leq \ell \leq 2 \cdot 10^5$) — the number of vertices, the number of edges, and the size of the multiset, respectively.

The second line of each test case contains $\ell$ integers $A_1, A_2, \ldots, A_{\ell}$ ($1 \leq A_i \leq 10^4$) — the elements of the multiset.

Each of the following $m$ lines contains two integers $u$ and $v$ ($1 \le u \lt v \le n$) — the endpoints of an edge in the graph.

It is guaranteed that the edges form a simple, connected graph without self-loops or multiple edges.

It is guaranteed that the sum of $n$, the sum of $m$, and the sum of $\ell$ over all test cases does not exceed $2 \cdot 10^5$, $4 \cdot 10^5$, and $2 \cdot 10^5$, respectively.

Output

For each test case, output a binary string of length $n$, where the $i$-th character is $\mathtt{1}$ if there exists a sequence of moves ending at vertex $i$, and $\mathtt{0}$ otherwise.

Note

In the first test case:

• Vertex $1$ is reachable without making any moves.
• Vertex $2$ is reachable by selecting element $3 \in A$; one possible walk is [$1 \rightarrow 2 \rightarrow 1 \rightarrow 2$].
• Vertex $3$ can be reached by selecting element $2 \in A$ and taking the walk [$1 \rightarrow 2 \rightarrow 3$].
• Vertex $4$ is reachable by selecting element $3 \in A$ and following the walk [$1 \rightarrow 2 \rightarrow 3 \rightarrow 4$].
• Vertex $5$ is not reachable by any valid sequence of moves.
• Vertex $6$ is reachable by first selecting element $2 \in A$ and taking the walk [$1 \rightarrow 2 \rightarrow 3$], followed by selecting element $3 \in A$ and taking the walk [$3 \rightarrow 4 \rightarrow 5 \rightarrow 6$].