Снежная корова Бесси
На ферму пришел снег, и Бесси, как обычно в начале каждой зимы, строит снежную корову! Большую часть времени Бесси стремится сделать свою скульптуру максимально похожей на настоящую корову. Однако в этом году, чувствуя художественное вдохновение, она решает пойти по более абстрактному пути и построить скульптуру в форме дерева, состоящую из n снежков, соединенных n - 1 ветвями. Каждая ветвь соединяет пару снежков. Между каждой парой снежков существует уникальный путь.
Бесси добавила нос к одному из снежков, так что он представляет собой голову абстрактной снежной коровы. Этот снежный ком она обозначила номер 1. Чтобы добавить больше визуального интереса, она планирует художественно покрасить некоторые снежки в разные цвета, наполнив старые молочные ведра цветным красителем и брызнув им на скульптуру. Цвета обозначаются целыми числами в диапазоне от 1 до 10^5, и у Бесси есть неограниченный запас ведер, заполненных красителями всех возможных цветов.
Когда Бесси брызгает на снежок ведром с краской, все снежки в его поддереве также заливаются этой же краской (снежок y находится в поддереве снежка x, если x лежит на пути от у к главному снежному кому). Разбрызгивая каждый цвет с большой осторожностью, Бесси следит за тем, чтобы все цвета, которыми был разбрызган снежный ком, остались видимыми. Например, если снежок имел цвета [1, 2, 3], а Бесси залила его цветом 4, то снежок будет иметь цвета [1, 2, 3, 4].
После того, как Бесси несколько раз обрызгает снежки, она может захотеть узнать, насколько красочна часть ее снежной коровы. "Красочность" снежного кома x равна количеству таких различных цветов c, которыми он окрашен. Если Бесси спросит вас о снежном коме x, Вы должны ответить, указав сумму значений красочности всех снежков в поддереве x.
Помогите Бесси найти красочность ее снежной коровы в определенные моменты времени.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 10^5) и количество запросов q (1 ≤ q ≤ 10^5). Каждая из следующих n - 1 строк содержит по два целых числа a и b, описывающих ветвь, соединяющую снежки a и b (1 ≤ a, b ≤ n).
Наконец, каждая из последующих q строк содержит запрос. Запрос вида
1 x c
указывает, что Бесси пролила ведро сока цвета c на снежок x, раскрасив все снежки в поддереве x. Строка вида
2 x
означает запрос суммы значений красочности всех снежков в поддереве x. Конечно, 1 ≤ x ≤ n и 1 ≤ c ≤ 10^5.
Выходные данные
Для каждого запроса типа 2 выведите сумму значений красочности в соответствующем поддереве. Обратите внимание, что Вы должны использовать 64-битные целые числа для избежания переполнения.
Пример
После первого запроса типа 1 снежный ком 4 окрашивается в цвет 1.
После второго запроса типа 1 снежки 4 и 5 окрашиваются в цвет 1.
После третьего запроса типа 1 все снежки окрашиваются в цвет 1.