Milk Visits on the Farm Tree

Farmer John plans to build $N$ farms connected by $N-1$ roads forming a tree, so every farm can reach any other farm without any cycles. Each farm houses a cow which is either a Guernsey (denoted by 'G') or a Holstein (denoted by 'H').

Farmer John's $M$ friends visit him. For the $i$-th friend, he travels along the unique path from farm $A_i$ to farm $B_i$ (note that $A_i$ and $B_i$ might be the same). During the visit, the friend can taste the milk of any cow along the path. Each friend has a strong preference and will only drink milk from a specific breed – some only drink Guernsey milk while others only drink Holstein milk. A friend is happy if and only if their preferred type of cow appears on the path they traverse.

inputFormat

The first line contains two integers $N$ and $M$, representing the number of farms and the number of friends respectively.

The second line is a string of length $N$ consisting only of characters 'G' and 'H'. The $i$-th character represents the type of cow at farm $i$.

Each of the next $N-1$ lines contains two integers $u$ and $v$, indicating that there is a road connecting farm $u$ and farm $v$.

The following $M$ lines each contain two integers $A_i$, $B_i$ and a character $P_i$ (either 'G' or 'H'), representing the starting farm, ending farm, and the friend’s preferred cow type respectively.

outputFormat

Output a binary string of length $M$. The $i$-th character of the string should be '1' if the $i$-th friend is happy (i.e. if the path from $A_i$ to $B_i$ contains at least one cow of type $P_i$) and '0' otherwise.

sample

4 3
GGGH
1 2
2 3
3 4
1 4 G
1 4 H
2 3 H

110