Фермер Джон побудував \(N\) (\(1 \leq N \leq 10^5\)) ферм, що з'єднані \(N-1\) дорогами, які формують дерево (тобто кожна ферма досяжна від будь-якої іншої, та відсутні цикли). Кожна ферма містить корів, чия порода Guernsey або Holstein.

\(M\) друзів ФД (\(1 \leq M \leq 10^5\)) часто відвідують його ферми. Під час візиту друга \(i\), ФД йде з цим другом за унікальним маршрутом від ферми \(A_i\) до ферми \(B_i\) (можливий випадок, коли \(A_i = B_i\)). Додатково вони можуть спробувати деяку кількість молока вздовж шляху, яким вони йдуть. Оскільки більшість друзів ФД самі фермери, вони мають сильні уподобання по молоку. Деякі з його друзів п'ють молоко тільки корів Guernsey, а решта п'ють лише молоко Holstein. Будь-який з друзів ФД буде щасливий тільки якщо він зможе попити молоко під час візиту.

Визначте, чи кожен друг залишиться щасливим після візиту.

ОЦІНЮВАННЯ:

• Тести 2-5 задовольняють \(N\le 10^3, M\le 2\cdot 10^3.\)

Формат вхідних даних

Перший рядок містить два цілих числа \(N\) і \(M\).

Другий рядок містить рядок довжину \(N\). \(i\)-ий символ рядка є 'G' якщо корова на \(i\)-ій фермі Guernsey, або 'H', якщо корова на \(i\)-ій фермі Holstein.

Кожна з наступних \(N-1\) рядків містить два цілих числа \(X\) і \(Y\) (\(1 \leq X, Y \leq N\)), що вказують, що існує дорога між фермами \(X\) та \(Y\).

Наступні \(M\) рядків містять цілі числа \(A_i\), \(B_i\) і символ \(C_i\). \(A_i\) і \(B_i\) представляють кінцеві точки шляху \(i\)'-го друга, а \(C_i\) або G або H - тип молока, який улюблений \(i\)-им другом.

Формат вихідних даних

Виведіть двійковий рядок довжини \(M\). \(i\)-ий символ рядка має бути '1' якщо \(i\)-ий друг буде щасливим, або '0' в іншому випадку.

Приклад вхідних даних

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

Приклад вихідних даних

10110