Nông dân John đang định xây ~N~ ~(1 \le N \le 10^5)~ trang trại được nối bởi ~N - 1~ con đường, tạo thành một đồ thị cây (mọi trang trại tới được nhau, và không tồn tại chu trình). Trang trại ~i~ có một trong hai giống bò là Holstein hoặc Guernsey.

Nông dân John có ~M~ ~(1 \le M \le 10^5)~ người bạn thường đến thăm anh ấy. Trong chuyến thăm của người bạn thứ ~i~, nông dân John sẽ cùng bạn mình đi trên các con đường từ trang trại ~A_i~ đến trang trại ~B_i~ (có thể ~A_i = B_i~). Hơn nữa, họ có thể uống sữa của bất kì con bò nào thuộc các trang trại dọc đường đi. Tuy nhiên, mỗi bạn của nông dân John chỉ thích uống sữa từ hoặc là giống bò Holstein hoặc là giống bò Guernsey. Các bạn của nông dân John sẽ chỉ cảm thấy vui nếu như họ có thể uống sữa từ giống bò họ thích.

Hãy xác định liệu mỗi bạn của John có cảm thấy vui sau chuyến thăm.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~.

• Dòng thứ hai chứa một xâu có độ dài ~N~. Kí tự thứ ~i~ của xâu là 'G' nếu trang trại ~i~ có giống bò Guernsey hoặc 'H' nếu trang trại ~i~ có giống bò Holstein.

• ~N - 1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~X~ và ~Y~ phân biệt ~(1 \le X, Y \le N)~ thể hiện tồn tại 1 con đường nối trang trại ~X~ và ~Y~.

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa các số nguyên ~A_i, B_i~ ~(1 \le A_i, B_i \le N)~ và kí tự ~C_i~. Trong đó ~A_i~ và ~B_i~ là hai đầu đường đi trong chuyến thăm của người bạn thứ ~i~, ~C_i~ bằng 'H' hoặc 'G' là giống bò mà người bạn thứ ~i~ thích.

Output

• In ra xâu nhị phân có độ dài ~M~. Kí tự thứ ~i~ của xâu là ~1~ nếu người bạn thứ ~i~ cảm thấy vui sau chuyến thăm, và ~0~ nếu ngược lại.

Sample Input 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

Sample Output 1

10110

Giải thích: Với chuyến thăm của người bạn thứ nhất và thứ hai, đường đi từ trang trại ~1~ đến trang trại ~4~ đi qua các trang trại: ~1~, ~2~ và ~4~. Tất cả trang trại này đều có giống bò Holsteins, do đó chỉ có người bạn thứ nhất cảm thấy vui, người bạn thứ hai thì không vui.

Ràng buộc

• Test 1 chính là test ví dụ.
• Test 2-5 có ~N \le 10^3, M \le 2 \cdot 10^3~.
• Các test còn lại không có thêm ràng buộc nào.