Ağacda quldurlar

$n$ şəhəri var və bu şəhərlər $1$-dən $n$-ə qədər nömrələnib. Şəhərlər bir-birinə $(n-1)$ yol ilə bağlıdır və hər bir şəhərdən digərinə çatmaq mümkündür. Hər yolun müəyyən bir uzunluğu var.

$i$ nömrəli şəhər $t_i$ zamanında $a_i$ nömrəli quldur klanı tərəfindən ələ keçirilmişdir ($1\le a_i\le n$). Şəhər $i$ ələ keçirildikdən sonra, yalnız $a_i$ klanının nümayəndələri oradan keçə bilər.

Aşağıdakı formada $m$ sualına cavab verin:

• u v b T — əgər $b$ klanının nümayəndəsi $T$ zamanında səyahətinə başlasa, $u$ şəhərindən $v$ şəhərinə keçə bilərmi? Əgər mümkün deyilsə, $u$-dan $v$-yə gedən yolda keçmək mümkün olmayan ilk şəhərin nömrəsini bildirin.

Giriş verilənləri

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

Sonrakı $(n-1)$ sətirin hər biri iki tam ədəd $p_i$ və $d_i$ ($1\le p_i<i$, $1\le d_i\le 10^3$) ehtiva edir, bu da $i$ və $p_i$ şəhərləri arasında $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$ ($1\le a_i\le 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$ ($1\le t_i\le 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\le m\le 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$, $v_i$, $b_i$, $T_i$ ($1\le u_i,v_i,b_i\le n$, $1\le T_i\le 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ış verilənləri

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

Qiymətləndirmə

1. ($7$ bal): $p_i=1$;

2. ($9$ bal): $n,m\le 10^3$;

3. ($11$ bal): $p_i=i-1,t_i=1$;

4. ($18$ bal): $p_i=i-1,a_i=1,b_i=2$;

5. ($15$ bal): $p_i=i-1$;

6. ($11$ bal): $t_i=1$;

7. ($17$ bal): $a_i=1,b_i=2$;

8. ($12$ bal): əlavə məhdudiyyətlər olmadan.