Беси с друзьями едет в горы. Гора имеет \(N\) точек пути,
(\(1\leq N \leq 10^5\)) помеченных \(1, 2, \ldots, N\)
в порядке возрастания высоты. (Точка 1 - основание горы).
Для каждой точки \(i > 1\), имеется лыжный маршрут, который
начинается в точке \(i\) и заканчивается в точке \(p_i\) (\(1\le p_i<i\)).
Этот маршрут имеет сложность \(d_i\) (\(0 \leq d_i \leq 10^9\))
и удовольствие \(e_i\) (\(0 \leq e_i \leq 10^9\)).
Каждый из \(M\) (\(1\leq M \leq 10^5\)) друзей Беси делает следующее:
выбирает начальную точку \(i\) затем двигается вниз в точку \(p_i\),
затем в точку \(p_{p_i}\) и т.д. пока не доберётся до точки \(1\).
Удовольствие каждого друга становится равным сумме удовольствий
маршрутов по которым он прошёл. Каждый друг имеет также уровень мастерства
\(s_j\) (\(0 \leq s_j \leq 10^9\)) и храбрости \(c_j\) (\(0 \leq c_j \leq 10\)),
которые ограничивают выбор начальной точки, чтобы двигаться не более чем по
\(c_j\) маршрутам со сложностью более чем \(s_j\).
Для каждого друга вычислите максимальное удовольствие, которое он может
получить.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Затем для каждого \(i\) от \(2\) до \(N\), следует строка, содержащая 3 разделённых
пробелами числа \(p_i\), \(d_i\), \(e_i\).
Следующая строка содержит \(M\).
Каждая из последующих \(M\) строк содержит два разделённых пробелом
целых числа sj\( и \)cj$.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите
\(M\) строк - ответ для каждого друга на отдельной строке.
В задаче могут потребоваться 64- битные
целые типы данных (например, "long long" в C/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 0
|
0
300
500
300
500
500
300
500
|