Farmer John định xây $N$ trang trại ($1 \leq N \leq 10^5$), nối bởi $N-1$ đường thành cây: mọi trang trại tới được nhau và không có chu trình. Mỗi trại có bò mang loại nguyên $T_i$ từ $1$ đến $N$ kể cả hai đầu.

$M$ bạn ($1 \leq M \leq 10^5$) thường tới thăm. Với bạn $i$, ông đi theo đường duy nhất từ $A_i$ đến $B_i$; có thể $A_i = B_i$. Họ có thể thử sữa của bất kỳ bò nào trên đường. Đa số bạn cũng là nông dân nên có sở thích mạnh; mỗi người chỉ uống sữa một loại bò và chỉ vui nếu uống được loại ưa thích trong chuyến thăm.

Hãy xác định từng bạn có vui sau chuyến thăm không.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$.

Dòng hai chứa $N$ số nguyên $T_1,T_2,\ldots, T_N$ cách nhau bằng dấu cách. Bò ở trại $i$ mang loại $T_i$.

$N-1$ dòng sau chứa hai số nguyên khác nhau $X$ và $Y$ ($1 \leq X, Y \leq N$), biểu thị cạnh giữa trại $X$ và $Y$.

$M$ dòng sau chứa $A_i$, $B_i$, $C_i$. $A_i$ và $B_i$ là hai đầu đường của bạn $i$; $C_i$ ($1\le C_i\le N$) là loại bò bạn thích.

Dữ liệu ra

In chuỗi nhị phân dài $M$. Ký tự thứ $i$ là '1' nếu bạn thứ $i$ vui, ngược lại '0'.

Ví dụ

Dữ liệu vào 1

5 5
1 1 2 1 2
1 2
2 3
2 4
1 5
1 4 1
1 4 2
1 3 2
1 3 1
5 5 1

Dữ liệu ra 1

10110

Ghi chú

Trong ví dụ, đường từ 1 đến 4 qua trại 1, 2, 4. Tất cả có bò loại 1, nên bạn đầu hài lòng còn bạn thứ hai không.

Dữ liệu vào 2

6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4

Dữ liệu ra 2

0110

Nhiệm vụ con

• Bộ kiểm thử thứ hai là ví dụ thứ hai bên dưới.
• Bộ thứ ba thỏa mãn $N\le 10^3, M\le 2\cdot 10^3$.
• Các bộ từ thứ tư đến thứ bảy thỏa mãn $C_i\le 10$ ($C_i$ định nghĩa bên dưới).

Tác giả bài toán: Spencer Compton