Nông dân John đang định xây \(N\) trang trại được nối bởi \(N-1\) con đường, tạo thành một đồ thị cây (mọi trang trại tới được nhau, và không tồn tại chu trình). Trang trại \(i\) có một loại bò là \(T_i\).

Nông dân John có \(M\) người bạn thường đến thăm anh ấy. Trong chuyến thăm của người bạn thứ \(i\), nông dân John sẽ cùng bạn mình đi trên các con đường từ trang trại \(A_i\) đến trang trại \(B_i\) (có thể \(A_i=B_i\)). Hơn nữa, họ có thể uống sữa của bất kì con bò nằm trên các trang trại dọc đường đi từ trang trại \(A_i\) đến trang trại \(B_i\). Tuy nhiên, bạn của nông dân John chỉ thích uống sữa từ một loại bò nhất định. Các bạn của nông dân John sẽ chỉ được thỏa mãn nếu như họ có thể uống sữa từ loại bò họ thích.

Hãy xác định liệu bạn của John có được thỏa mãn sau chuyến thăm.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương \(N,M\) \((1 \le N,M \le 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(T_1,T_2,...T_N\) là loại bò của mỗi trang trại \((1 \le T_i \le N)\)
• \(N-1\) dòng tiếp theo chứa \(2\) số nguyên \(X\) và \(Y\) phân biệt \((1 \le X,Y \le N)\) thể hiện tồn tại 1 con đường nối trang trại \(X\) và \(Y\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa các số nguyên \(A_i,B_i\) và \(C_i\). Trong đó \(A_i, B_i\) là hai đầu chuyến thăm của người bạn thứ \(i\), \(C_i\) là loại bò mà người bạn thứ \(i\) thích \((1 \le A_i,B_i,C_i \le N)\)

Dữ liệu ra

• In ra xâu nhị phân có độ dài \(M\). Kí tự thứ \(i\) của xâu là \(1\) nếu người bạn thứ \(i\) được thỏa mãn, và \(0\) nếu ngược lại.

Input 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

Output 1

10110

Input 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

Output 2

0110