给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。树的每个顶点都被赋予了一个非负整数权值。

我们将从树中删除一些边。删除后，对于每个连通分量，其顶点权值之和必须在区间 $[L, R]$ 内。

对于所有整数 $0 \le i \le K$，请确定是否可以通过删除恰好 $i$ 条边来实现这一目标。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例，每个测试用例的格式如下：

每个测试用例的第一行包含四个整数 $N, K, L$ 和 $R$ ($1 \le N \le 1000, 0 \le K \le \min(50, N - 1), 0 \le L \le R \le 10^{18}$)。

下一行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，其中 $A_i$ 表示顶点 $i$ 的权值 ($0 \le A_i \le 10^{18}$)。

接下来的 $N - 1$ 行，每行包含两个整数 $x, y$，表示连接顶点 $x$ 和 $y$ 的边 ($1 \le x, y \le N, x \neq y$)。保证给定的图是一棵树。

所有测试用例的 $N$ 之和不超过 $1000$。

输出格式

对于每个测试用例，输出一个长度为 $K + 1$ 的二进制字符串。如果可以通过删除恰好 $i - 1$ 条边来实现目标，则第 $i$ 个字符应为 '1'，否则为 '0'。

样例

输入 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

输出 1

0111
0011
0000