Существует $n$ городов, пронумерованных от $1$ до $n$. Все города соединены с помощью $(n - 1)$ дорог так, что от каждого города можно добраться до каждого. Каждая дорога имеет определенную длину. Известно, что город с номером $i$ был захвачен кланом бандитов с номером $a_i$ ($1 \leq a_i \leq n$) в момент времени $t_i$. После захвата города $i$ (то есть, начиная с момента времени $t_i$ \textbf{включительно}), через него могут проходить только представители клана $a_i$. Ответьте на $m$ вопросов следующего вида: \begin{itemize} \item \t{u v b T} --- сможет ли представитель клана $b$ попасть из города $u$ в город $v$, если он начнет свое путешествие в момент времени $T$. В случае невозможности совершения путешествия, необходимо также сообщить номер первого города на пути от $u$ до $v$, через который невозможно проехать. \end{itemize} \InputFile Первая строка содержит целое число $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$) --- номера начального и конечного городов очередного пути, номер клана путешественника, и момент времени начала путешествия соответственно. \OutputFile Для каждого запроса выведите в отдельной строке одно целое число --- номер первого города на пути от $u$ до $v$, через который невозможно пройти. Если такого города не существует, выведите <<\t{-1}>>. Обратите внимание на большой объем входных и выходных данных в этой задаче. Советуем использовать быстрые средства ввода и вывода, например \t{scanf/printf} вместо \t{cin/cout} в языке \t{C ++} и \t{sys.stdin.readline} вместо \t{input} в \t{Python}. Также советуем использовать интерпретатор \t{PyPy} при решении задачи на \t{Python}. \Scoring \begin{enumerate} \item ($7$ баллов): $p_i = 1$; \item ($9$ баллов): $n, m \leq 10^3$; \item ($11$ баллов): $p_i = i - 1, t_i = 1$; \item ($18$ баллов): $p_i = i - 1, a_i = 1, b_i = 2$; \item ($15$ баллов): $p_i = i - 1$; \item ($11$ баллов): $t_i = 1$; \item ($17$ баллов): $a_i = 1, b_i = 2$; \item ($12$ баллов): без дополнительных ограничений. \end{enumerate}