존(Farmer John) 아저씨는 N개의 목장을 건설할 계획입니다. 이 목장들은 N-1개의 도로로 연결되어 있으며, 트리(Tree) 구조를 이룹니다.

즉, 모든 목장은 서로 이동 가능하며 사이클(순환 경로)이 존재하지 않습니다. 각 목장에는 한 마리의 소가 살고 있으며, 소의 품종은 건지(Guernsey) 또는 홀스타인(Holstein) 중 하나입니다.

존 아저씨에게는 M명의 친구가 있고, 이들은 종종 아저씨를 방문합니다. i번째 친구가 방문하면, 존 아저씨는 그 친구와 함께 목장 Ai에서 목장 Bi까지 이어지는 유일한 최단 경로를 따라 산책을 합니다 (Ai = Bi일 수도 있습니다).

산책하는 동안, 그들은 경로 상에 있는 임의의 목장에서 짜낸 우유를 맛볼 수 있습니다.

존 아저씨의 친구들은 대부분 농부이기 때문에 우유에 대한 취향이 매우 확고합니다.

어떤 친구들은 건지 우유('G')만 마시고, 나머지 친구들은 홀스타인 우유('H')만 마십니다.

친구들은 산책 경로에 있는 목장 중 최소한 한 곳 이상에서 자신이 선호하는 품종의 우유를 마실 수 있어야만 만족합니다.

각 친구가 방문을 마친 후 만족할 수 있을지 여부를 판단하는 프로그램을 작성하세요.

입력

첫째 줄에 목장의 수 N과 친구들의 수 M이 공백으로 구분되어 주어집니다. (1 <= N, M <= 100,000)

둘째 줄에 길이가 N인 문자열이 주어집니다. 문자열의 i번째 문자는 i번째 목장에 있는 소의 품종을 나타내며, 건지라면 'G', 홀스타인이라면 'H'입니다. (목장 번호는 1번부터 시작합니다.)

셋째 줄부터 N-1개의 줄에 걸쳐 각 줄에 두 개의 서로 다른 정수 X와 Y가 주어집니다. 이는 목장 X와 목장 Y 사이에 도로가 있음을 의미합니다. (1 <= X, Y <= N)

그 다음 M개의 줄에 걸쳐 각 줄에 두 정수 Ai, Bi와 문자 Ci가 공백으로 구분되어 한 줄에 하나씩 주어집니다. Ai와 Bi는 산책 경로의 양 끝점(목장 번호)을 나타내고, Ci는 해당 친구가 선호하는 우유의 종류('G' 또는 'H')입니다.

출력

질문이 들어온 순서대로, 각 친구가 만족하면 '1', 만족하지 못하면 '0'을 표현하는 길이 M인 이진 문자열을 한 줄에 출력합니다.

예제 입력 1

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

예제 출력 1

10110

힌트

여기서 1번 목장과 4번 목장을 잇는 경로에는 1번, 2번, 4번 목장이 포함됩니다. 이 목장들에는 모두 홀스타인(H) 품종만 있기 때문에, 첫 번째 친구는 만족하지만 두 번째 친구는 만족하지 못합니다.

출처

USACO 2019 December Contest, Silver