Бандити на дереві

Існує $n$ міст, пронумерованих від $1$ до $n$. Усі міста з'єднані за допомогою $(n-1)$ доріг так, що від кожного міста можна дістатися до кожного. Кожна дорога має певну довжину.

Відомо, що місто з номером $i$ було захоплено кланом бандитів з номером $a_i$ ($1\le a_i\le n$) в момент часу $t_i$. Після захоплення міста $i$ (тобто, починаючи з моменту часу $t_i$ включно), через нього можуть проходити тільки представники клану $a_i$.

Дайте відповідь на $m$ запитань наступного вигляду:

• u v b T — чи зможе представник клану $b$ пройти від міста $u$ до міста $v$, якщо він розпочне свою подорож у час $T$. У випадку неможливості здійснення подорожі, необхідно також сказати номер першого міста на шляху від $u$ до $v$, через яке неможливо буде пройти.

Вхідні дані

Перший рядок містить єдине ціле число $n$ ($2\le n\le 10^5$) — кількість міст.

Кожен з наступних $(n-1)$ рядків містить два цілі числа $p_i$ та $d_i$ ($1\le p_i<i$, $1\le d_i\le 10^3$), що позначають дорогу між містами $i$ та $p_i$ довжиною $d_i$. Індексація починається з $2$.

Наступний рядок містить $n$ цілих чисел $a_i$ ($1\le a_i\le n$), що позначають номера кланів, що захопили відповідне місто.

Наступний рядок містить $n$ цілих чисел $t_i$ ($1\le t_i\le 10^9$), що позначають моменти часу захоплення кожного міста.

Наступний рядок містить єдине ціле число $m$ ($1\le m\le 10^5$) — кількість запитань.

Останні $m$ рядків описують запитання. Кожен з них містить чотири цілі числа $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$) — номера початкового та фінішного міст чергового шляху, номер клану мандрівника, та момент часу початку подорожі відповідно.

Вихідні дані

Для кожного запитання виведіть в окремому рядку єдине ціле число — номер першого міста на шляху від $u$ до $v$, через яке неможливо буде пройти. Якщо такого міста не існує, виведіть «-1».

Зверніть увагу на великий об'єм вхідних та вихідних даних у цій задачі. Радимо використовувати швидкі засоби введення та виведення, наприклад scanf/printf замість cin/cout у мові C++, та sys.stdin.readline замість input у Python. Також радимо використовувати інтерпретатор PyPy при розв'язанні задачі на Python.

Приклади

Оцінювання

1. ($7$ балів): $p_i=1$;

2. ($9$ балів): $n,m\le 10^3$;

3. ($11$ балів): $p_i=i-1,t_i=1$;

4. ($18$ балів): $p_i=i-1,a_i=1,b_i=2$;

5. ($15$ балів): $p_i=i-1$;

6. ($11$ балів): $t_i=1$;

7. ($17$ балів): $a_i=1,b_i=2$;

8. ($12$ балів): без додаткових обмежень.