该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Milk Visits S

题目描述

$Farmer$ $John$计划建造$N$（$1 \leq N \leq 10^{5}$）个农场，用$N-1$条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。

$Farmer$ $John$的$M$个朋友（$1 \leq M \leq 10^{5}$）经常前来拜访他。在朋友$i$拜访之时，$Farmer$ $John$会与他的朋友沿着从农场$A_{i}$到农场$B_{i}$之间的唯一路径行走（可能有$A_{i}=B_{i}$）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于$Farmer$ $John$的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何$Farmer$ $John$的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

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

输入格式

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

第二行包含一个长为$N$的字符串。如果第$i$个农场中的奶牛是更赛牛，则字符串中第$i$个字符为$G$，如果第$i$个农场中的奶牛是荷斯坦牛则为$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}$是$G$或$H$之一，表示第$i$个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

输出格式

输出一个长为$M$的二进制字符串。如果第$i$个朋友会感到高兴，则字符串的第$i$个字符为$1$，否则为$0$。

数据范围与提示

测试点$2$-$5$满足$N \leq 10^{3}$，$M \leq 2 \times 10^{3}$。

样例

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