Ağacda quldurlar

Giriş

Birinci sətir $n$ ( $2 \leq n \leq 1 0^{5}$ 2 \leq n \leq 10^5) tək tam ədədini ehtiva edir — şəhərlərin sayı.

Sonrakı $(n - 1)$ (n - 1) sətirin hər biri iki tam ədəd $p_{i}$ p_i və $d_{i}$ d_i ( $1 \leq p_{i} < i$ 1 \leq p_i < i, $1 \leq d_{i} \leq 1 0^{3}$ 1 \leq d_i \leq 10^3) ehtiva edir, bu da $i$ və $p_{i}$ p_i şəhərləri arasında $d_{i}$ d_i uzunluğunda yolu göstərir. İndeksləmə $2$ -dən başlayır.

Növbəti sətir $n$ tam ədəd $a_{i}$ a_i ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) ehtiva edir, bu da müvafiq şəhəri ələ keçirən klanların nömrələrini göstərir.

Növbəti sətir $n$ tam ədəd $t_{i}$ t_i ( $1 \leq t_{i} \leq 1 0^{9}$ 1 \leq t_i \leq 10^9) ehtiva edir, bu da hər bir şəhərin ələ keçirilmə zamanını göstərir.

Növbəti sətir $m$ ( $1 \leq m \leq 1 0^{5}$ 1 \leq m \leq 10^5) tək tam ədədini ehtiva edir — sualların sayı.

Son $m$ sətir sualları təsvir edir. Hər biri dörd tam ədəd $u_{i}$ u_i, $v_{i}$ v_i, $b_{i}$ b_i, $T_{i}$ T_i ( $1 \leq u_{i}, v_{i}, b_{i} \leq n$ 1 \leq u_i, v_i, b_i \leq n, $1 \leq T_{i} \leq 1 0^{9}$ 1 \leq T_i \leq 10^9) ehtiva edir — başlanğıc və son şəhərlərin nömrələri, səyahətçinin klan nömrəsi və səyahətin başlanğıc zamanı müvafiq olaraq.

Çıxış

Hər bir sual üçün ayrı sətirdə tək tam ədəd çıxarın — $u$ -dan $v$ -yə gedən yolda keçmək mümkün olmayan ilk şəhərin nömrəsi. Əgər belə bir şəhər yoxdursa, «-1» çıxarın.

Bu məsələdə böyük həcmli giriş və çıxış məlumatlarına diqqət yetirin. C++ dilində cin/cout əvəzinə scanf/printf və Python dilində input əvəzinə sys.stdin.readline kimi sürətli giriş və çıxış vasitələrindən istifadə etməyi tövsiyə edirik. Həmçinin, Python dilində məsələnin həlli zamanı PyPy interpretatorundan istifadə etməyi tövsiyə edirik.

Nümunələr

Nümunə 1

Loading

Nümunə 2

Loading

Nümunə 3

Loading

Bal hesablama

( $7$ bal): $p_{i} = 1$ p_i = 1;
( $9$ bal): $n, m \leq 1 0^{3}$ n, m \leq 10^3;
( $11$ bal): $p_{i} = i - 1, t_{i} = 1$ p_i = i - 1, t_i = 1;
( $18$ bal): $p_{i} = i - 1, a_{i} = 1, b_{i} = 2$ p_i = i - 1, a_i = 1, b_i = 2;
( $15$ bal): $p_{i} = i - 1$ p_i = i - 1;
( $11$ bal): $t_{i} = 1$ t_i = 1;
( $17$ bal): $a_{i} = 1, b_{i} = 2$ a_i = 1, b_i = 2;
( $12$ bal): əlavə məhdudiyyətlər olmadan.