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

Вхідні дані

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

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

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

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

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

Останні $m$ рядків описують запитання. Кожен з них містить чотири цілі числа u_i, v_i, b_i, T_i (1 \leq u_i, v_i, b_i \leq n, 1 \leq T_i \leq 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 \leq 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$ балів): без додаткових обмежень.