题目描述

给定一棵 $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$ 。

样例

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

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}$ 。

时间限制：$\texttt{3s}$

空间限制：$\texttt{1024MB}$