Statement is not available in English language
4. Задача D. Настолка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Нашим друзьям стало скучно ждать второго тура, и они решили порыскать по шкафчикам, которые находились в комнате. В одном из шкафчиков Максим нашел бордово-белую коробку, на которой было написано "BOBR".

Это оказалась настольная игра. Игра проходила на карте, которая представляла собой связный граф без циклов из $$$n$$$ вершин и $$$n-1$$$ ребер, то есть представляло дерево с корнем в вершине $$$1$$$. На каждой вершине $$$i$$$ изначально записано целое неотрицательное число $$$a_i$$$.

Пусть $$$pr_{v, 0}$$$ — сама вершина $$$v$$$, $$$pr_{v, 1}$$$ — прямой предок вершины $$$v$$$, тогда $$$pr_{v, k}$$$ — $$$k$$$-ый предок вершины $$$v$$$.

Не вникая сильно в правила игры, игрок может делать $$$2$$$ типа операций с этим деревом:

  • $$$\; ? \; v$$$ — вывести значение в $$$v$$$-ой вершине.
  • $$$\; + \; v\; k\; x$$$ — прибавить $$$x$$$ к значениям вершин $$$pr_{v, 0}$$$, $$$pr_{v, k}$$$, $$$pr_{v, 2 \cdot k}$$$ и т.д. .

Поскольку друзья устали после первого тура, выполните за них $$$q$$$ операций.

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

Первая строка содержит два целых числа $$$n$$$, $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^5$$$) — количество вершин в дереве и количество операций соответственно.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$, обозначающие две вершины, соединённые ребром ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$). Гарантируется, что данные рёбра образуют дерево.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$0 \leq a_i \leq 5 \cdot 10^3$$$), разделенных пробелами — описание изначальных значений вершин.

Далее следуют $$$q$$$ строк, задающих запросы. Каждая строка задается одним из следующих форматов:

  • $$$\; ? \; v$$$ — обозначает, что очередной запрос первого типа — ($$$1 \le v \le n$$$).
  • $$$\; + \; v\; k\; x$$$ — обозначает, что очередной запрос второго типа — ($$$1 \le v \le n$$$, $$$1 \le k \le n$$$, $$$0 \le x \le 5 \cdot 10^3$$$).
Выходные данные

На каждый запрос второго типа выведите одно целое число — значение в вершине $$$v$$$.

Система оценки
№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$n, q \le 10^3$$$$$$4$$$
$$$2$$$$$$u_i = i, v_i = i+1$$$$$$22$$$
$$$3$$$$$$k = 1$$$$$$10$$$
$$$4$$$Все запросы $$$1$$$ типа идут после запросов $$$2$$$$$$24$$$
$$$5$$$$$$n \le 10^5$$$$$$11$$$$$$1$$$
$$$6$$$Нет дополнительных ограничений$$$29$$$$$$1$$$ — $$$5$$$
Пример
Входные данные
5 5
1 2
2 3
3 4
1 5
1 2 4 8 11
+ 3 2 5
? 1
? 2
+ 5 1 7
? 1
Выходные данные
6
2
13