题目描述

$Bob$ 去珍珠市场闲逛，市场上有 $n$ 个商家，商家之间通过 $n-1$ 条道路连通，即任意两个商家之间都有一条简单路径连通。(路径上的各顶点均不互相重复，称这样的路径为简单路径)

这些商家有的销售黑珍珠，有的销售白珍珠，用一个长度为 $n$ 由 B 和 W 构成的字符串 $S$ 表示商家的销售类型 。 $S_i$ 表示第 $i$ 个商家的销售类型，$S_i$=B 表示黑珍珠，$S_i$=W 表示白珍珠。

$Bob$ 做了 $m$ 个闲逛计划，每份计划包括闲逛的起点和终点，以及想购买的珍珠类型，对于这 $m$ 份计划，$Bob$ 想知道从起点到终点的简单路径上，是否能购买到他想购买的珍珠。

输入格式

第一行，两个整数 $n$ $m$

第二行，包含一个长度为 $n$ 由 B 和 W 组成的字符串，表示商家的销售类型。

接下来 $n-1$ 行，两个整数 $x$ $y$ ,表示商家 $x$ 与 $y$ 之间连接一条边。

接下来 $m$ 行，每行两个整数和一个字符构成，整数 $a_i$ $b_i$ 表示起点和终点，一个字符 B 或 W 表示希望购买类型。

输出格式

一个长度为 $m$ 的由 0 或 1 构成的字符串，第 $i$ 个计划可以实现，字符串第 $i$ 个字符就是 1 ,否则就是 0

5 5
BBWBW
1 2
2 3
2 4
1 5
1 4 B
1 4 W
1 3 W
1 3 B
5 5 B

10110

数据规模与约定

$Subtask1$： $1 \le n \le 10^3, 1 \le m \le 10^3$, $50$ 分

$Subtask2$： $1 \le n \le 10^5, 1 \le m \le 10^5$ , $50$ 分