Farmer John 计划建造 N（1≤N≤10⁵）个农场，用 N−1 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为 1 到 N 之间的一个整数 Ti。 

Farmer John 的 M 个朋友（1≤M≤10⁵）经常前来拜访他。在朋友 i 拜访之时，Farmer John 会与他的朋友沿着从农场Ai 到农场Bi 之间的唯一路径行走（可能有 Ai=Bi）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的每个朋友都只喝某种特定品种的奶牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

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

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

第二行包含 N 个空格分隔的整数 T1,T2,…,TN。第 i 个农场内的奶牛的品种用 Ti 表示。

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

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