给定一棵 n 个点的树，点编号从 1 到 n 。每个点有一个非负权值 ai 。
你需要把树上的一些边删掉。你需要保证，删掉之后，每个连通块的权值之和在区间 [L,R] 中。
给定非负整数 K ，对于每个 0≤i≤K ，判断能否恰好删去 i 条边。
输入格式
第一行，一个正整数 T ，表示数据组数，之后对于每组数据：
- 第一行四个非负整数 n,K,L,R 。
- 第二行 n 个非负整数 a1,⋯,an 。
- 接下来 n−1 行，每行两个正整数 x,y ，表示树上的一条边。
输出格式
对于每组数据：
- 一行，一个长度为 K+1 的字符串 s ，其中 si 在可以恰好删去 i−1 条边时为 1 ，否则为 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≤T≤1000，1≤n,∑n≤1000，0≤K≤min，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}