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

Существует $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$ баллов): без дополнительных ограничений.