给定一棵 $n$ 个点的树，点编号从 $1$ 到 $n$ 。每个点有一个非负权值 $a_i$ 。
你需要把树上的一些边删掉。你需要保证，删掉之后，每个连通块的权值之和在区间 $[L,R]$ 中。
给定非负整数 $K$ ，对于每个 $0\le i\le K$ ，判断能否恰好删去 $i$ 条边。
输入格式
第一行，一个正整数 $T$ ，表示数据组数，之后对于每组数据：
- 第一行四个非负整数 $n,K,L,R$ 。
- 第二行 $n$ 个非负整数 $a_1,\cdots,a_n$ 。
- 接下来 $n-1$ 行，每行两个正整数 $x,y$ ，表示树上的一条边。
输出格式
对于每组数据：
- 一行，一个长度为 $K+1$ 的字符串 $s$ ，其中 $s_i$ 在可以恰好删去 $i-1$ 条边时为 $\texttt{1}$ ，否则为 $\texttt 0$ 。
样例一
input
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
0111 0011 0000
样例二
见下发文件，该样例符合子任务 $3$ 的限制。
样例三
见下发文件，该样例符合子任务 $4$ 的限制。
样例四
见下发文件，该样例符合子任务 $5$ 的限制。
数据范围与提示
对于所有数据，$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}$ 。
| 子任务编号 | 特殊限制 | 分值 |
|---|---|---|
| $1$ | $\sum n\le 30$，$R\le 80$ | $15$ |
| $2$ | $\sum n\le 100$，$R\le 200$ | $15$ |
| $3$ | $\sum n\le 500$，$R-L\le 600$ | $20$ |
| $4$ | 存在一个点的度数为 $n-1$ | $15$ |
| $5$ | $ $ | $35$ |
时间限制：$\texttt{3s}$
空间限制：$\texttt{1024MB}$