Існує $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}