Трудно поверить, но Джейми — финальный босс!
У Джейми есть дерево на n вершинах, пронумерованных от 1 до n. Изначально корнем дерева является вершина с номеров 1. Кроме того, на каждой вершине дерева записано число.
Вам необходимо обрабатывать запросы трёх типов:
1 v — Сделать вершину с номером v корнем дерева.
2 u v x — Прибавить x к значению каждой вершины наименьшего по размеру поддерева, содержащего вершины u и v.
3 v — Найти сумму значений вершин в поддереве вершины v.
Поддерево вершины v — это множество вершин, для которых v лежит на кратчайшем пути от этой вершины до корня. Обратите внимание, что поддерево вершины может измениться в результате изменения корня дерева.
Покажите Джейми вашу мощь и выполните все запросы!
Выходные данные
Для каждого запроса третьего типа выведите ответ на него. Гарантируется, что в тесте есть хотя бы один запрос третьего типа.
Примечание
Картинка ниже иллюстрирует изменения дерева в первом тестовом примере.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 7
1 4 2 8 5 7
1 2
3 1
4 3
4 5
3 6
3 1
2 4 6 3
3 4
1 6
2 2 4 -5
1 4
3 3
|
27
19
5
|
|
2
|
4 6
4 3 5 6
1 2
2 3
3 4
3 1
1 3
2 2 4 3
1 1
2 2 4 -3
3 1
|
18
21
|