Máte daný strom s ohodnotenými hranami a otázky na dvojice vrcholov. Sú dva typy otázok. Pri prvej otázke chceme zistiť číslo $k$-teho vrcholu na ceste, a pri druhej chceme zistiť dĺžku cesty.
Prvý riadok obsahuje číslo $n$ ($1 \leq n \leq 10^5$) udávajúce počet vrcholov stromu. Vrchol číslo $0$ je koreň. Nasleduje $n-1$ riadkov, kde $i$-ty riadok udáva otca vrcholu $i$ a dĺžku hrany do tohto otca $d_i$ ($1 \leq d_i \leq 100$).
Tretí riadok obsahuje číslo $q$ ($1 \leq q \leq 10^6$): počet otázok. Nasleduje $q$ riadkov, každý obsahuje jednu otázku. Otázky sú tvaru $KTH~a~b~k$ a $DST~a~b$ kde $a$ a $b$ sú čísla vrcholov a $k$ je menšie ako počet vrcholov na ceste z $a$ do $b$.
Pre každú otázku typu KTH a b k vypíšte jeden riadok obsahujúci
číslo $k$-teho vrchola na ceste z $a$ do $b$. ($a$ je nultý vrchol
na tejto ceste.)
Pre každú otázku typu DST a b vypíšte jeden riadok, obsahujúci dĺžku
najkratšej cesty z $a$ do $b$. (Pod dĺžkou cesty rozumieme súčeť dĺžok
hrán na ceste.)
5
0 1
0 2
1 3
1 4
7
DST 3 4
KTH 2 3 3
KTH 0 4 2
DST 0 2
DST 1 2
KTH 3 3 0
DST 4 4
7
3
4
2
3
3
0