Farmer John planeja construir $N$ fazendas ($1 \leq N \leq 10^5$), ligadas por $N-1$ estradas formando uma árvore: todas alcançáveis entre si, sem ciclos. Cada fazenda tem uma vaca de tipo inteiro $T_i$ entre $1$ e $N$ inclusive.

Seus $M$ amigos ($1 \leq M \leq 10^5$) o visitam frequentemente. Com o amigo $i$, caminha pelo único caminho de $A_i$ a $B_i$; pode ser $A_i = B_i$. Podem provar leite de qualquer vaca no caminho. A maioria também é fazendeira e tem preferências fortes: cada amigo bebe apenas leite de certo tipo de vaca e só ficará feliz se puder beber seu favorito durante a visita.

Determine se cada amigo ficará feliz após a visita.

Entrada

A primeira linha contém os inteiros $N$ e $M$.

A segunda contém $N$ inteiros $T_1,T_2,\ldots, T_N$ separados por espaços. A vaca da fazenda $i$ é de tipo $T_i$.

As próximas $N-1$ linhas contêm dois inteiros distintos $X$ e $Y$ ($1 \leq X, Y \leq N$), indicando uma aresta entre as fazendas $X$ e $Y$.

As próximas $M$ linhas contêm $A_i$, $B_i$, $C_i$. $A_i$ e $B_i$ são os extremos do caminho do amigo $i$, e $C_i$ ($1\le C_i\le N$) o tipo de vaca preferido.

Saída

Imprima uma string binária de comprimento $M$. O caractere $i$ é '1' se o amigo $i$ ficará feliz, e '0' caso contrário.

Exemplos

Entrada 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

Saída 1

10110

Nota

No exemplo, o caminho de 1 a 4 passa pelas fazendas 1, 2 e 4. Todas têm vacas de tipo 1, portanto o primeiro amigo fica satisfeito, mas o segundo não.

Entrada 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

Saída 2

0110

Subtarefas

• O caso dois é o segundo exemplo abaixo.
• O caso três satisfaz $N\le 10^3, M\le 2\cdot 10^3$.
• Os casos quatro a sete satisfazem $C_i\le 10$ ($C_i$ definido abaixo).

Autor do problema: Spencer Compton