E. Девочка и задача про дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Девочка очень любит задачи про деревья. Вот одна из них.

Дерево — это неориентированный связный граф без циклов. Степень вершины x в дереве — это количество вершин y дерева таких, что каждая из них связана с вершиной x каким-то ребром дерева.

Рассмотрим дерево, состоящее из n вершин. Будем считать, что вершины этого дерева пронумерованы от 1 до n. Рассматриваемое дерево обладает следующим свойством: каждая вершина, кроме вершины с номером 1, имеет степень не более 2.

Изначально в каждой вершине дерева записано число 0. Ваша задача — быстро выполнять запросы двух типов:

  • Запрос вида: 0 v x d. В ответ на запрос нужно добавить x ко всем числам, записанным в вершинах, которые находятся на расстоянии не более чем d от вершины с номером v. Расстоянием между двумя вершинами будем считать количество ребер на кратчайшем пути между ними.
  • Запрос вида: 1 v. В ответ на запрос нужно вывести текущее число, записанное в вершине с номером v.
Входные данные

В первой строке заданы числа n (2 ≤ n ≤ 105) и q (1 ≤ q ≤ 105) — количество вершин дерева и количество запросов, соответственно.

Каждая из следующих n  -  1 строк содержит два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), которые обозначают, что существует ребро между вершинами с номерами ui и vi. Описание каждого ребра встречается во входных данных ровно один раз. Гарантируется, что заданный граф — дерево, обладающее свойством, которое описано в условии.

Следующие q строк описывают запросы.

  • Запрос на добавление имеет следующий формат: 0 v x d (1 ≤ v ≤ n, 1 ≤ x ≤ 104, 1 ≤ d < n).
  • Запрос на вывод значения, записанного в вершине, имеет следующий формат: 1 v (1 ≤ v ≤ n).

Числа в строках разделяются одиночными пробелами.

Выходные данные

Для каждого запроса на вывод значения, записанного в вершине, выведите целое число — ответ на запрос.

Примеры
Входные данные
3 6
1 2
1 3
0 3 1 2
0 2 3 1
0 1 5 2
1 1
1 2
1 3
Выходные данные
9
9
6
Входные данные
6 11
1 2
2 5
5 4
1 6
1 3
0 3 1 3
0 3 4 5
0 2 1 4
0 1 5 5
0 4 6 2
1 1
1 2
1 3
1 4
1 5
1 6
Выходные данные
11
17
11
16
17
11