Молочные посещения (Серебро)
Фермер Джон планирует построить 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. Все они содержат Голштинов, поэтому первый друг будет доволен, а второй нет.