Вам задано дерево, состоящее из \(n\) вершин. Первоначально в каждой вершине записано число \(0\).
Вам нужно обработать \(m\) запросов двух видов:
- Вам задан номер вершины \(v\). Выведите значение в данной вершине \(v\).
- Вам заданы номера вершин \(u\) и \(v\), и значения \(k\) и \(d\) (\(d \le 20\)). Вам нужно прибавить \(k\) к значению каждой вершины, расстояние от которой до пути из \(u\) в \(v\) не превосходит \(d\).
Расстояние между двумя вершинами \(x\) и \(y\) равно количеству ребер на пути из \(x\) в \(y\). Например, расстояние от \(x\) до самой \(x\) равно \(0\).
Расстояние от вершины \(v\) до некоторого пути из \(x\) в \(y\) равно минимуму из расстояний от \(v\) до любой вершины на пути из \(x\) в \(y\).
Выходные данные
Для каждого запроса первого типа выведите текущее значение в заданной вершине.
Примечание
Дерево из первого примера:
Описания некоторых запросов:
- «\(2\) \(4\) \(5\) \(10\) \(2\)»: попадающие под прибавление вершины — это \(\{4, 2, 5, 1, 3\}\);
- «\(2\) \(1\) \(1\) \(10\) \(20\)» и «\(2\) \(6\) \(6\) \(10\) \(20\)»: все вершины попадают под прибавление, так как расстояние до \(1\) (\(6\)) меньше \(20\) у любой вершины;
- «\(2\) \(3\) \(2\) \(10\) \(0\)»: попадающие под прибавление вершины — это \(\{3, 1, 2\}\);
- «\(2\) \(5\) \(2\) \(10\) \(1\)»: попадающие под прибавление вершины — это \(\{5, 2, 4, 1\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2
1 3
4 2
5 2
3 6
14
2 4 5 10 2
1 3
1 6
2 1 1 10 20
2 6 6 10 20
1 3
2 3 2 10 0
2 5 2 10 1
1 1
1 2
1 3
1 4
1 5
1 6
|
10
0
30
50
50
40
40
40
20
|