El granjero John planea construir ~N~ granjas conectadas por ~N-1~ caminos, formando un árbol (es decir, todas las granjas son accesibles entre sí y no hay ciclos). Cada granja tiene una vaca de raza Guernsey o Holstein.

Los ~M~ amigos del granjero John lo visitan con frecuencia. Durante una visita con el amigo ~i~, el granjero John caminará con él por un camino único que va desde la granja ~A_i~ hasta la granja ~B_i~ (es posible que ~A_i = B_i~). Además, podrán probar la leche de cualquier vaca que encuentren en el camino. Como la mayoría de los amigos del granjero John también son granjeros, tienen preferencias muy marcadas en cuanto a la leche. Algunos solo beben leche Guernsey, mientras que otros solo beben leche Holstein. Cualquiera de los amigos del granjero John solo estará contento si puede beber su tipo de leche preferido durante su visita.

Determina si cada amigo estará contento después de la visita.

Entrada

• La primera línea contiene los dos enteros ~N~ y ~M~.
• La segunda línea contiene una cadena de caracteres de longitud ~N~. El i-ésimo carácter de la cadena es 'G' si la vaca de la i-ésima granja es de raza Guernsey, o 'H' si es de raza Holstein.
• Las siguientes ~N-1~ líneas contienen dos enteros distintos ~X~ e ~Y~, que indican la existencia de un camino entre las granjas ~X~ e ~Y~.
• Las siguientes ~M~ líneas contienen los enteros ~A_i, B_i~ y el carácter ~C_i~. ~A_i~ y ~B_i~ representan los extremos del camino recorrido durante la visita del amigo ~i~, mientras que ~C_i~ indica el tipo de vaca cuya leche consume el amigo.

Salida

Imprime una cadena binaria de longitud ~M~. El i-ésimo carácter de la cadena debe ser '1' si el i-ésimo amigo estará contento, o '0' en caso contrario.

Restricciones

• ~1 \leq N \leq 10^5~
• ~1 \leq M \leq 10^5~
• ~1 \leq C_i \leq N~
• ~1 \leq X,Y \leq N~

Ejemplo de Entrada

5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H

Ejemplo de Salida

10110

En este caso, el camino desde la granja 1 hasta la granja 4 incluye las granjas ~1, 2~ y ~4~. Todas ellas contienen vacas Holstein, por lo que el primer amigo estará contento, mientras que el segundo no.

USACO 2019 December Contest, Silver. Problem 3. Milk Visits.