Девочка очень любит задачи про деревья. Вот одна из них.
Дерево — это неориентированный связный граф без циклов. Степень вершины x в дереве — это количество вершин y дерева таких, что каждая из них связана с вершиной x каким-то ребром дерева.
Рассмотрим дерево, состоящее из n вершин. Будем считать, что вершины этого дерева пронумерованы от 1 до n. Рассматриваемое дерево обладает следующим свойством: каждая вершина, кроме вершины с номером 1, имеет степень не более 2.
Изначально в каждой вершине дерева записано число 0. Ваша задача — быстро выполнять запросы двух типов:
- Запрос вида: 0 v x d. В ответ на запрос нужно добавить x ко всем числам, записанным в вершинах, которые находятся на расстоянии не более чем d от вершины с номером v. Расстоянием между двумя вершинами будем считать количество ребер на кратчайшем пути между ними.
- Запрос вида: 1 v. В ответ на запрос нужно вывести текущее число, записанное в вершине с номером v.
Выходные данные
Для каждого запроса на вывод значения, записанного в вершине, выведите целое число — ответ на запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|