우유 방문

Farmer John은 $N$ ($1 \leq N \leq 10^5$)개의 농장을 지으려고 하며, 이 농장들은 $N-1$개의 도로로 연결되어 트리를 이룬다. 즉, 모든 농장은 서로 도달 가능하고 사이클이 없다. 각 농장에는 소가 한 마리씩 있고, 그 품종은 Guernsey 또는 Holstein 중 하나이다.

Farmer John에게는 $M$명의 친구 ($1 \leq M \leq 10^5$)가 자주 방문한다. 친구 $i$의 방문 동안 Farmer John은 친구와 함께 농장 $A_i$에서 농장 $B_i$까지 도로를 따라 유일한 경로를 걷는다. $A_i = B_i$일 수도 있다. 또한 걸어가는 경로에 있는 어떤 소의 우유든 시음할 수 있다. Farmer John의 친구 대부분은 농부이기도 해서 우유에 대한 선호가 매우 확고하다. 어떤 친구는 Guernsey 우유만 마시고, 나머지는 Holstein 우유만 마신다. Farmer John의 친구는 방문 중에 자신이 선호하는 종류의 우유를 마실 수 있어야만 만족한다.

각 친구가 방문 후 만족하는지 판별하시오.

첫째 줄에 두 정수 $N$과 $M$이 주어진다.

둘째 줄에 길이가 $N$인 문자열이 주어진다. 문자열의 $i$번째 문자가 'G'이면 $i$번째 농장의 소가 Guernsey이고, 'H'이면 Holstein이다.

다음 $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$가 Guernsey 우유를 선호하면 G, Holstein 우유를 선호하면 H이다.

길이가 $M$인 이진 문자열을 출력한다. 문자열의 $i$번째 문자는 $i$번째 친구가 만족하면 '1', 그렇지 않으면 '0'이다.

여기서 농장 1과 농장 4 사이의 경로는 농장 1, 2, 4를 지난다. 이 농장들에는 모두 Holstein이 있으므로 첫 번째 친구는 만족하고 두 번째 친구는 만족하지 않는다.