Farmer John planea construir $N$ granjas ($1 \leq N \leq 10^5$), unidas por $N-1$ caminos formando un árbol: todas son accesibles entre sí y no hay ciclos. Cada granja tiene una vaca de tipo entero $T_i$ entre $1$ y $N$ inclusive.

Sus $M$ amigos ($1 \leq M \leq 10^5$) lo visitan a menudo. Con el amigo $i$ camina por la única ruta de $A_i$ a $B_i$; puede ser $A_i = B_i$. Pueden probar leche de cualquier vaca de la ruta. La mayoría también son granjeros y tienen fuertes preferencias: cada uno solo bebe leche de cierto tipo de vaca y estará feliz únicamente si puede beber su favorita en la visita.

Determina si cada amigo estará feliz tras la visita.

Entrada

La primera línea contiene los enteros $N$ y $M$.

La segunda contiene $N$ enteros $T_1,T_2,\ldots, T_N$ separados por espacios. La vaca de la granja $i$ es de tipo $T_i$.

Las siguientes $N-1$ líneas contienen dos enteros distintos $X$ y $Y$ ($1 \leq X, Y \leq N$), que indican una arista entre las granjas $X$ y $Y$.

Las siguientes $M$ líneas contienen $A_i$, $B_i$, $C_i$. $A_i$ y $B_i$ son los extremos de la ruta del amigo $i$, y $C_i$ ($1\le C_i\le N$) su tipo de vaca favorito.

Salida

Imprime una cadena binaria de longitud $M$. El carácter $i$ es '1' si el amigo $i$ estará feliz, y '0' en caso contrario.

Ejemplos

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

Salida 1

10110

Nota

En el ejemplo, la ruta de 1 a 4 pasa por las granjas 1, 2 y 4. Todas tienen vacas de tipo 1, así que el primer amigo estará satisfecho y el segundo no.

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

Salida 2

0110

Subtareas

• El caso dos es el segundo ejemplo de abajo.
• El caso tres cumple $N\le 10^3, M\le 2\cdot 10^3$.
• Los casos cuatro a siete cumplen $C_i\le 10$ ($C_i$ definido abajo).

Autor del problema: Spencer Compton