Bessie se va de viaje de esquí con sus amigas. La montaña tiene ~N~ puntos de referencia numerados del ~1~ al ~2,\ldots, N~ en orden creciente de altitud (el punto de referencia ~1~ es la base de la montaña).

Para cada punto de referencia ~i > 1~, existe una pista de esquí que comienza en el punto de referencia ~i~ y termina en el punto de referencia ~p_i~. Esta pista tiene una dificultad ~d_i~ y un nivel de disfrute ~e_i~.

Cada uno de los ~M~ amigos de Bessie hará lo siguiente: Elegirá un punto de referencia inicial ~i~ para comenzar y luego seguirá las carreras en orden descendente (hasta ~p_i~, luego hasta p_{pi}, y así sucesivamente) hasta llegar al punto de referencia 1.

El disfrute que obtiene cada amigo es igual a la suma de los disfrutes de las carreras que sigue. Cada amigo también tiene un nivel de habilidad ~s_j~ y un nivel de valentía ~c_j~ diferentes, lo que les limita a seleccionar un punto de referencia inicial que les permita realizar como máximo ~c_j~ carreras con una dificultad mayor que ~s_j~. Para cada amigo, calcula el máximo disfrute que puede obtener.

Entrada

• La primera línea contiene ~N~.
• Luego, para cada ~i~ del ~2~ al ~N~, sigue una línea con tres enteros separados por espacios: ~p_i~, ~d_i~ y ~e_i~.
• La siguiente línea contiene ~M~.
• Las siguientes ~M~ líneas contienen dos enteros separados por espacios: ~s_j~ y ~c_j~.

Salida

Imprimir ~M~ líneas, con la respuesta para cada amigo en una línea aparte. Tenga en cuenta que el gran tamaño de los enteros involucrados en este problema puede requerir el uso de tipos de datos enteros de 64 bits (por ejemplo, un long long en C/C++).

Restricciones

• ~1 \leq N \leq 10^5~
• ~1 \leq p_i < i~
• ~0 \leq d_i \leq 10^9~
• ~0 \leq e_i \leq 10^9~
• ~1 \leq M \leq 10^5~
• ~0 \leq s_j \leq 10^9~
• ~0 \leq c_j \leq 10~

Ejemplo de Entrada

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

Ejemplo de Salida

0
300
500
300
500
500
300
500

El primer amigo no puede comenzar en ningún punto de ruta que no sea el 1, ya que cualquier otro punto de ruta le obligaría a realizar al menos una partida con una dificultad superior a 19. Su disfrute total es 0.

El segundo amigo puede comenzar en el punto de ruta 4 y realizar partidas hasta el punto de ruta 2 y luego hasta el 1. Su disfrute total es 100 + 200 = 300. Realizan una partida con una dificultad superior a 19.

El tercer amigo puede comenzar en el punto de referencia 3 y realizar partidas hasta el punto de referencia 2 y luego hasta el 1. Su disfrute total es de 300 + 200 = 500. Realizan dos partidas con una dificultad superior a 19.

USACO 2025 US Open Contest, Silver. Problem 3. Ski Slope.