Farmer John은 $N$개($1 \leq N \leq 10^5$) 농장을 $N-1$개 길로 연결한 트리를 만들 계획입니다. 모든 농장은 서로 도달 가능하고 사이클이 없습니다. 각 농장에는 $1$ 이상 $N$ 이하의 정수 종류 $T_i$인 소가 있습니다.

$M$명($1 \leq M \leq 10^5$) 친구들이 자주 방문합니다. 친구 $i$가 오면 농장 $A_i$에서 $B_i$까지 유일한 경로를 걷습니다. $A_i = B_i$일 수도 있습니다. 경로의 어떤 소의 우유든 맛볼 수 있습니다. 대부분 친구도 농부라 강한 취향이 있고 특정 종류의 소의 우유만 마십니다. 방문 동안 좋아하는 우유를 마실 수 있어야만 행복합니다.

방문 후 각 친구가 행복할지 판단하세요.

입력

첫 줄에는 두 정수 $N$과 $M$이 주어집니다.

둘째 줄에는 공백 구분된 $N$개 정수 $T_1,T_2,\ldots, T_N$이 주어집니다. $i$번째 농장의 소 종류는 $T_i$입니다.

다음 $N-1$개 줄에는 서로 다른 정수 $X$와 $Y$($1 \leq X, Y \leq N$)가 주어지고, 농장 $X$와 $Y$ 사이의 간선을 뜻합니다.

다음 $M$개 줄은 정수 $A_i$, $B_i$, $C_i$입니다. $A_i$와 $B_i$는 친구 $i$의 경로 양 끝점이며, $C_i$($1\le C_i\le N$)는 좋아하는 소 종류입니다.

출력

길이 $M$의 이진 문자열을 출력하세요. $i$번째 친구가 행복하면 $i$번째 문자는 '1', 아니면 '0'입니다.

예제

입력 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

출력 1

10110

참고

예제에서 1부터 4까지의 경로는 농장 1, 2, 4를 지납니다. 모두 종류 1의 소가 있어서 첫 친구는 만족하고 둘째는 아닙니다.

입력 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

출력 2

0110

서브태스크

• 테스트 케이스 둘은 아래의 두 번째 예제입니다.
• 테스트 케이스 셋은 $N\le 10^3, M\le 2\cdot 10^3$을 만족합니다.
• 테스트 케이스 넷부터 일곱까지는 $C_i\le 10$을 만족합니다($C_i$는 아래 정의).

문제 작성자: Spencer Compton