8. Divné diery

Po výbornom farmárskom výkone v minulom kole, sa aj Farmári z Matfyzu vybrali na výlet do Legolandu. Po tom ako sa pár krát stratili v spleti uličiek, jeden zavelil: “Kašlime na to. Spravme z Legolandu strom, nech sa tu nedá zablúdiť.” Rozhodli sa teda, že niektoré cesty v Legolande zastavajú tak aby vznikol strom. Chvíľu rozmýšlali či to spravili optimálne, ale zrazu sa vyskytol oveľa väčší problém.

V Legolande je zopár divných dier v časopriestore, ktoré fungujú takto: Po tom čo kozmickej bytosti zaplatíš \(c\) vesmírnych peňazí, ocitneš sa o \(w\) sekúnd v mieste, kde sa diera nachádza a to bez ohladu na to, kde si sa predtým nachádzal. Toto Farmárom otvorilo nové možnosti prepravovania sa v Legolande a teraz ich zaujíma, ako sa vedia za nejaký čas dostať z vchodu do Legolandu napríklad do miestnej lego farmy, alebo na najbližší burger. Keďže však sú študenti, potrebujú to spraviť za čo najmenej vesmírnych peňazí, aby im to ešte fakulta preplatila. Farmári nie sú moc dobrí programátori, preto niet divu, že táto úloha pripadla na vás.

Úloha

Legoland je strom, teda súvislý graf s \(n\) vrcholmi a \(n - 1\) hranami. Vstup do Legolandu, kde sa nachádzajú Farmári teraz, je vo vrchole \(0\), v tomto vrchole strom zakoreníme. Pre každú hranu \(i\) vieme číslo \(t_i\) – čas v sekundách, ktorý trvá prejsť ju Farmárom peši.

V Legolande je \(m \leq n\) dier v časopriestore. Diera \(i\) sa nachádza vo vrchole \(v_i \leq n\) a poznáme pre ňu ešte 2 hodnoty: \(c_i\) – cena, ktorú musia Farmári zaplatiť kozmickej bytosti, a \(w_i\) – čas v sekundách, ktorý musia Farmári čakať, kým sa premiestnia do vrcholu \(v_i\). Všimnite si, že to nezávisí od toho, kde sa práve Farmári nachádzajú (hovoril som, že diery v časopriestore sú divné?)

Farmári si vybrali \(q\) zaujímavých miest, \(a_1,\dots,a_q\) a na \(i\)-te z nich by sa chceli dostať z vrcholu \(0\) za \(b_i\) času. Vašou úlohou je zistiť, či a za koľko najmenej peňazí sa na miesto \(a_i\) vedia dostať v časovom limite \(b_i\).

Formát vstupu

Na prvom riadku vstupu je číslo \(T\) popisujúce počet testov. Nasleduje \(T\) testov, pred každým z nich je prázdny riadok.

Na prvom riadku testu je číslo \(n\) (\(1\leq n \leq 10^5\)) – počet vrcholov v strome.

Na druhom riadku je popis stromu: \(n - 1\) čísel \(p_1,\dots,p_{n-1}\) oddelených medzerou. Číslo \(p_i\) (\(0\leq p_i < i\)) popisuje, že otec vrcholu s číslom \(i\) je vrchol \(p_i\). (Vrcholy číslujeme od \(0\). Vrchol \(0\) nemá otca, lebo je koreň.) Je zaručené, že žiaden vrchol nemá za otca vrchol s väčším číslom.

Na treťom riadku sú zadané časy na prejdenie hrán: \(n - 1\) čísel \(t_1,\dots,t_{n-1}\) oddelených medzerou. Číslo \(t_i\) (\(1\leq t_i \leq 10^9\)) popisuje čas v sekundách, aký trvá prejdenie z vrcholu \(i\) do jeho otca (a naopak).

Na štvrtom riadku je číslo \(m\) (\(1\leq m\leq 10^5\)) – počet dier.

Nasleduje \(m\) riadkov, \(i\)-ty z nich obsahuje 3 čísla \(v_i, c_i, w_i\) oddelené medzerou (\(0\leq v_i < n\), \(1\leq c_i, w_i\leq 10^9\)): postupne vrchol v ktorom sa diera nachádza, cena vo vesmírnych peniazoch a čas v sekundách aký trvá kým sa do diery premiestnite (viac dier môže byť v tom istom vrchole)

Na nasledujúcom riadku je číslo \(q\) (\(1\leq q \leq 10^5\)) – počet otázok.

Nasleduje \(q\) riadkov. Na \(i\)-tom z nich sú 2 čísla \(a_i, b_i\) (\(0\leq a_i < n\), \(1\leq b_i \leq 10^9\)) – postupne vrchol, kam sa chcú Farmári dostať a ako najdlhšie to môže trvať.

Formát výstupu

Pre každú otázku vypíšte jeden riadok a v ňom jedno číslo – koľko najmenej peňazí musia Farmári použiť, na to aby sa dostali z vrcholu \(0\) do cieľa v časovom limite, prípadne \(-1\), ak sa tam v časovom limite dostať nevedia.

Hodnotenie

Sú 4 sady vstupov, za každú sú 2 body. Nech \(C\) označuje najväčšie z čísel na vstupe a \(H\) hĺbku stromu¹, potom v jednotlivých sadách platia nasledujúce obmedzenia:

Súčet hodnôt \(n\) vo všetkých testoch nepresiahne \(10^5\). Rovnako aj súčet hodnôt \(m\) a \(q\).

Príklady

Input:

1

2
0
2
1
1 1 1
2
1 2
1 1

Output:

0
1

Pri prvej otázke sa dá v časovom limite prejsť do cieľa peši, preto je odpoveď 0. Pri druhej otázke musíme použiť dieru vo vrchole 1, tá má cenu 1.

Input:

2

5
0 1 2 3
4 7 8 6
3
0 7 3
4 2 3
2 1 10
3
3 7
4 14
2 10

5
0 0 2 1
3 1 3 4
2
4 6 2
4 3 3
3
4 2
4 3
4 7

Output:

-1
2
1
6
3
0