Сніжна корова Бессі
На ферму випав сніг, і Бессі, як завжди на початку зими, будує снігову корову! Зазвичай вона намагається зробити свою скульптуру максимально схожою на справжню корову. Але цього року, відчувши натхнення, вона вирішила створити абстрактну скульптуру у формі дерева, що складається з n сніжків, з'єднаних n - 1 гілкою. Кожна гілка з'єднує пару сніжків, і між будь-якими двома сніжками існує унікальний шлях.
Бессі додала ніс до одного з сніжків, щоб він представляв голову абстрактної снігової корови. Цей сніжок вона позначила номером 1. Щоб додати більше візуального інтересу, вона планує художньо пофарбувати деякі сніжки в різні кольори, використовуючи старі молочні відра, наповнені кольоровим барвником, і розбризкуючи його на скульптуру. Кольори позначаються цілими числами від 1 до 10^5, і у Бессі є необмежений запас відер з барвниками всіх можливих кольорів.
Коли Бессі бризкає на сніжок відром з фарбою, всі сніжки в його піддереві також заливаються цією ж фарбою (сніжок y знаходиться в піддереві сніжка x, якщо x лежить на шляху від y до головного сніжка). Розбризкуючи кожен колір з великою обережністю, Бессі стежить за тим, щоб усі кольори, якими був розбризканий сніжок, залишалися видимими. Наприклад, якщо сніжок мав кольори [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.