Молочні відвідування (Срібло)
Фермер Джон планує побудувати n ферм, які будуть з'єднані n - 1 дорогами, утворюючи дерево (тобто всі ферми досяжні одна з одної, циклів немає). На кожній фермі є корова породи Гернсі або Голштин.
m друзів фермера Джона часто навідують його. Під час візиту друга i фермер Джон буде йти з ним по унікальному набору доріг від ферми A[i] до ферми B[i] (можливо A[i] = B[i]). Крім того, вони можуть спробувати молока від будь-якої корови на своєму шляху. Оскільки більшість друзів фермера Джона також є фермерами, у них дуже сильні уподобання щодо молока. Деякі з його друзів будуть пити тільки молоко Гернсі, а решта будуть пити тільки молоко Голштин. Будь-який з друзів фермера Джона буде щасливий лише в тому випадку, якщо зможе випити улюблений сорт молока під час свого візиту.
Визначте, чи буде щасливий кожен друг в результаті візиту.
Вхідні дані
Перша рядок містить два цілих числа n (1 ≤ n ≤ 10^5) і m (1 ≤ m ≤ 10^5). Друга рядок містить рядок довжини n. i - ий символ рядка дорівнює 'G', якщо корова на i - й фермі Гернсі, і 'H', якщо корова на i - й фермі Голштинська.
Наступні n - 1 рядок містять по два різних цілих числа x і y (1 ≤ x, y ≤ 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' в іншому випадку.
Приклад
Шлях від ферми 1 до ферми 4 включає ферми 1, 2 і 4. Всі вони містять Голштинів, тому перший друг буде задоволений, а другий ні.