Given a tree with $n$ nodes, labeled from $1$ to $n$. Each node has a non-negative weight $a_i$.

You need to remove some edges from the tree. You must ensure that after the removal, the sum of weights in each connected component is within the interval $[L, R]$.

Given a non-negative integer $K$, for each $0 \le i \le K$, determine whether it is possible to remove exactly $i$ edges.

Input

The first line contains a positive integer $T$, representing the number of test cases. For each test case:

• The first line contains four non-negative integers $n, K, L, R$.
• The second line contains $n$ non-negative integers $a_1, \dots, a_n$.
• The next $n-1$ lines each contain two positive integers $x, y$, representing an edge in the tree.

Output

For each test case:

• A single line containing a string $s$ of length $K+1$, where $s_i$ is $\texttt{1}$ if it is possible to remove exactly $i-1$ edges, and $\texttt{0}$ otherwise.

Examples

Input 1

3
4 3 1 2
1 1 1 1
1 2
2 3
3 4
4 3 1 2
1 1 1 1
1 2
1 3
1 4
4 3 0 0
1 1 1 1
1 2
1 3
1 4

Output 1

0111
0011
0000

Input 2

See the provided file; this sample satisfies the constraints of Subtask 3.

Output 2

See the provided file.

Input 3

See the provided file; this sample satisfies the constraints of Subtask 4.

Output 3

See the provided file.

Input 4

See the provided file; this sample satisfies the constraints of Subtask 5.

Output 4

See the provided file.

Constraints

For all test cases, $1 \le T \le 1000$, $1 \le n, \sum n \le 1000$, $0 \le K \le \min(50, n-1)$, $0 \le L \le R \le 10^{15}$, $0 \le a_i \le 10^{15}$.