가짜 플라스틱 나무 2

정점이 $N$개인 트리가 주어진다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있다. 이 트리는 정점 가중치가 있는 트리이며, 각 정점에는 0 이상의 정수 가중치가 할당되어 있다.

트리의 간선 일부를 삭제한다. 삭제한 뒤 각 연결 요소에 속한 정점 가중치의 합이 $[L, R]$ 범위에 들어가야 한다.

$0 \le i \le K$인 모든 정수 $i$에 대해, 정확히 $i$개의 간선을 삭제해서 이 목표를 달성할 수 있는지 판별한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 다음 형식으로 $T$개의 테스트 케이스가 주어진다.

첫 줄에 정수 $N$, $K$, $L$, $R$이 주어진다.

다음 줄에 정수 $N$개 $A_1, A_2, \ldots, A_N$이 주어지며, $A_i$는 정점 $i$의 가중치이다.

다음 $N-1$개의 줄에는 간선으로 연결된 두 정점 $x$, $y$가 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 길이가 $K + 1$인 이진 문자열을 출력한다. $i$번째 문자는 정확히 $i-1$개의 간선을 삭제해서 목표를 달성할 수 있으면 1, 그렇지 않으면 0이다.

• $1 \le N \le 1\,000$
• $0 \le K \le \min(50, N - 1)$
• $0 \le L \le R \le 10^{18}$
• $0 \le A_i \le 10^{18}$
• $1 \le x, y \le N$
• $x \neq y$
• 주어지는 그래프는 트리이다.
• 모든 테스트 케이스에 대해 $N$의 합은 $1\,000$ 이하이다.