eolymp
bolt
Try our new interface for solving problems
Problems

Milk Visits (Silver)

Milk Visits (Silver)

Time limit 1 second
Memory limit 128 MiB

Farmer John is planning to build n farms that will be connected by n1 roads, forming a tree (i.e., all farms are reachable from each-other, and there are no cycles). Each farm contains a cow, whose breed is either Guernsey or Holstein.

Farmer John's m friends often come to visit him. During a visit with friend i, Farmer John will walk with his friend along the unique path of roads from farm A[i] to farm B[i] (it may be the case that A[i] = B[i]). Additionally, they can try some milk from any cow along the path they walk. Since most of Farmer John's friends are also farmers, they have very strong preferences regarding milk. Some of his friends will only drink Guernsey milk, while the remainder will only drink Holstein milk. Any of Farmer John's friends will only be happy if they can drink their preferred type of milk during their visit.

Please determine whether each friend will be happy after visiting.

Input data

The first line contains two integers n (1n10^5) and m (1m10^5). The second line contains a string of length n. The i-th character of the string is 'G' if the cow in the i-th farm is a Guernsey, or 'H' if the cow in the i-th farm is a Holstein.

The next n1 lines each contain two distinct integers x and y (1x, yn), indicating that there is a road between farms x and y.

The next m lines contain integers A[i], B[i] and a character C[i]. A[i] and B[i] represent the endpoints of the path walked during friend i's visit, while C[i] is either G or H if the i-th friend prefers Guernsey milk or Holstein milk.

Output data

Print a binary string of length m. The i-th character of the string should be '1' if the i-th friend will be happy, or '0' otherwise.

Example

Here, the path from farm 1 and farm 4 involves farms 1, 2 and 4. All of these contain Holsteins, so the first friend will be satisfied while the second one will not.

Examples

Input example #1
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
Output example #1
10110
Source 2019 USACO December Silver