우유 취향

한 농부가 $N$ ($1 \leq N \leq 10^5$)개의 농장을 건설할 계획이며, 이들을 $N-1$개의 도로로 연결해 트리 형태(즉, 모든 농장들은 서로에게 도달할 수 있고, 순환이 없음)를 형성할 예정입니다. 각 농장에는 건지 또는 홀스타인 품종의 한 마리의 소가 있습니다.

농부의 $M$명의 친구들 ($1 \leq M \leq 10^5$)은 자주 그를 방문하러 옵니다. $i$번째 친구와의 방문 시, 농부는 친구와 함께 $A_i$ 농장에서 $B_i$ 농장으로 향하는 도로의 고유한 경로를 따라 걸을 것입니다($A_i = B_i$ 일 수 있음).

 또한, 그들은 걷는 길에 있는 소의 우유를 맛볼 수 있습니다. 농부의 대부분의 친구들 또한 농부들이므로, 그들은 우유에 대해 매우 뚜렷한 선호도를 가지고 있습니다. 그의 친구들 중 일부는 오직 건지 우유만 마시고, 나머지는 홀스타인 우유만 마십니다. 농부의 친구들은 방문하는 동안 자신들이 선호하는 유형의 우유를 마실 수 있다면 만족 할 것입니다.

각 친구가 방문 후 행복해질지 여부를 판단해 주세요.

첫 번째 줄에는 두 정수 $N$과 $M$이 포함됩니다.

두 번째 줄에는 길이가 $N$인 문자열이 포함됩니다. 문자열의 $i$번째 문자는 i번째 농장의 소가 건지라면 'G', 홀스타인이라면 'H'입니다.

다음 $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$는 $i$번째 친구가 건지 우유를 선호하면 G, 홀스타인 우유를 선호하면 H입니다.

길이가 $M$인 이진 문자열을 출력하십시오. 문자열의 $i$번째 문자는 $i$번째 친구가 행복할 경우 '1' 아니면 '0'이어야 합니다.