You are given a tree with $N$ vertices numbered from $1$ to $N$. The tree is vertex-weighted. In other words, each vertex of the tree is assigned a nonnegative integer weight.

We will delete some edges from the tree. After the deletion, for each connected component, the sum of vertex weights should be in the range $[L, R]$.

For all integers $0 \le i \le K$, determine if we can achieve this goal by deleting exactly $i$ edges.

Input

The first line contains a single integer $T$, the number of test cases. Then $T$ test cases follow, each following the given specification:

The first line of each test case contains four integers $N$, $K$, $L$, and $R$ ($1 \le N \le 1000$, $0 \le K \le \min(50, N - 1)$, $0 \le L \le R \le 10^{18}$).

The next line contains $N$ integers $A_1, A_2, \ldots, A_N$, where $A_i$ denotes the weight of vertex $i$ ($0 \le A_i \le 10^{18}$).

Each of the next $N-1$ lines contains two integers $x, y$, denoting the pair of vertices connected by an edge ($1 \le x, y \le N$, $x \neq y$). It is guaranteed that the given graph is a tree.

For all test cases, the sum of $N$ is at most $1000$.

Output

For each test case, output a binary string of length $K + 1$. The $i$-th character should be 1 if it is possible to achieve the desired goal by deleting exactly $i-1$ edges. Otherwise, the $i$-th character should be 0.

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