You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

Farmer John 计划建造 N 个农场，用 N−1 条道路连接，构成一棵树。

每个农场有一头奶牛，这些奶牛要么是蒙牛的，要么是伊利的。

Farmer John 的 M 个朋友经常前来拜访他。在朋友 i 拜访之时，Farmer John 会与他的朋友沿着从农场Ai到农场 Bi之间的唯一路径行走（可能有Ai=Bi）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。

由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更蒙牛的牛产的牛奶，其余的只喝伊利的牛产的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

【输入格式】

输入的第一行包含两个整数 N 和 M。

第二行包含一个长为 N 的字符串。如果第 i 个农场中的奶牛是蒙牛的，则字符串中第 i 个字符为 G，如果第 i 个农场中的奶牛是伊利的则为 H。

以下 N−1 行，每行包含两个不同的整数 X 和 Y（1≤X,Y≤N），表示农场 X 与 Y 之间有一条道路。

以下 M 行，每行包含整数 Ai，Bi，以及一个字符 Ci。Ai和 Bi表示朋友 i 拜访时行走的路径的端点，Ci是 G 或 H 之一，表示第 i 个朋友喜欢更蒙牛的牛奶或是伊利的牛奶。

【输出格式】

输出一个长为 M 的二进制字符串。

如果第 i 个朋友会感到高兴，则字符串的第 i 个字符为 1，否则为 0。

【输入样例】

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

【输出样例】 10110

【样例1 说明】

第1个朋友，从农场 1 到农场 4 的路径包括农场 1、2、4，这些农场的奶牛都是伊利的，所以第一个朋友可以任选一个位置品尝到自己喜欢的牛奶，会感到高兴。

第2个朋友无法品尝到自己喜欢的牛奶，不会感到高兴。

第3个朋友，从农场1到农场3的路径包括农场1、2、3，这些农场的奶牛分别是伊利、伊利、蒙牛，所以朋友3会感到高兴。

第4个朋友也会感到高兴。

第5个朋友，从农场5到农场5的路径包括农场5，这个农场的奶牛是蒙牛的，因此他无法品尝到自己喜欢的牛奶，所以朋友5不会感到高兴。

【数据范围】

对于40%的数据， N≤10^3，M≤2*10^3。

对于100%的数据，1≤N,M≤10^5。