Farmer John vuole costruire $N$ fattorie ($1 \leq N \leq 10^5$), connesse da $N-1$ strade in un albero: tutte raggiungibili tra loro e senza cicli. Ogni fattoria ha una mucca di tipo intero $T_i$ tra $1$ e $N$ inclusi.

I suoi $M$ amici ($1 \leq M \leq 10^5$) lo visitano spesso. Con l'amico $i$, percorre l'unico cammino da $A_i$ a $B_i$; può essere $A_i = B_i$. Possono assaggiare il latte di qualsiasi mucca sul cammino. La maggior parte degli amici è anche agricoltore e ha forti preferenze: ciascuno beve solo latte di un certo tipo di mucca e sarà felice solo se potrà bere quello preferito durante la visita.

Determina se ogni amico sarà felice dopo la visita.

Input

La prima riga contiene gli interi $N$ e $M$.

La seconda contiene $N$ interi $T_1,T_2,\ldots, T_N$ separati da spazi. La mucca della fattoria $i$ ha tipo $T_i$.

Le successive $N-1$ righe contengono due interi distinti $X$ e $Y$ ($1 \leq X, Y \leq N$), indicando un arco tra le fattorie $X$ e $Y$.

Le successive $M$ righe contengono $A_i$, $B_i$, $C_i$. $A_i$ e $B_i$ sono gli estremi del cammino dell'amico $i$, e $C_i$ ($1\le C_i\le N$) il suo tipo di mucca preferito.

Output

Stampa una stringa binaria di lunghezza $M$. Il carattere $i$ è '1' se l'amico $i$ sarà felice, altrimenti '0'.

Esempi

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

Spiegazione

Nell'esempio il cammino da 1 a 4 attraversa le fattorie 1, 2 e 4. Tutte hanno mucche di tipo 1, quindi il primo amico è soddisfatto, il secondo no.

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

Sottoproblemi

• Il caso due è il secondo esempio sotto.
• Il caso tre soddisfa $N\le 10^3, M\le 2\cdot 10^3$.
• I casi da quattro a sette soddisfano $C_i\le 10$ ($C_i$ definito sotto).

Autore del problema: Spencer Compton