Вам дано корневое дерево с \(n\) вершинами. Вершины нумеруются от \(1\) до \(n\); корнем является вершина \(1\).
С каждой вершиной связаны два числа: \(a_i\) и \(b_i\). Обозначим множество всех предков \(v\) (включая саму вершину \(v\)) как \(R(v)\). Обозначим крутость вершины \(v\) как
\(\)\left| \sum_{w \in R(v)} a_w\right| \cdot \left|\sum_{w \in R(v)} b_w\right|,\(\)
где \(|x|\) обозначает абсолютную величину \(x\).
Нужно выполнить \(q\) запросов двух типов:
- 1 v x — увеличить \(a_v\) на положительное число \(x\).
- 2 v — найти максимальную крутость в поддереве вершины \(v\).
Выходные данные
Для каждого запроса второго типа нужно в отдельной строке вывести максимальную крутость в соответствующем поддереве.
Примечание
Начальная крутость вершин равна \([100, 91, 57, 64, 57]\). Самая крутая вершина в поддереве вершины \(1\) (первый запрос) — это вершина \(1\), а самая крутая вершина в поддереве вершины \(2\) (второй запрос) — это вершина \(2\).
После первого обновления (третий запрос), крутость вершин станет равна \([100, 169, 57, 160, 57]\), и поэтому самая крутая вершина во всем дереве (четвертый запрос) теперь \(2\).
После второго обновления (пятый запрос), крутость вершин станет равна \([100, 234, 57, 240, 152]\), поэтому самая крутая вершина (шестой запрос) теперь \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
1 1 2 2
10 -3 -7 -3 -10
10 3 9 3 6
2 1
2 2
1 2 6
2 1
1 2 5
2 1
|
100
91
169
240
|