给你一棵含有 $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, \ldots, A_N$，其中 $A_i$ 表示节点 $i$ 的权值（$0 \le A_i \le 10^{18}$）。

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

对于所有测试用例，所有 $N$ 的总和不超过 $1000$。

输出格式

对于每个测试用例，输出一个长度为 $K + 1$ 的二进制字符串。如果可以通过恰好删除 $i-1$ 条边来达到目标，则第 $i$ 个字符（$1$-based）应为 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