\begin{problem}{Любовь к комбинаторным объектам}{стандартный ввод}{стандартный вывод}{1 секунда}{256 мегабайт}

Саша очень любит комбинаторику и считает, что в любом контесте должна быть задача на неё. К несчастью, ни его друзья, ни друзья его друзей так не считают.

После того, как Саша дал задачу на комбинаторику на Очень Важную Олимпиаду, всеобщее терпение рухнуло, и теперь каждый хочет публично озвучить свою неприязнь к комбинаторике. Саша, с другой стороны, готов её защищать, и если кто-то из его друзей напишет ему, что задач на комбинаторику не должно быть на школьных олимпиадах, Саша проведёт с ним воспитательную беседу, и начиная со следующего дня этот человек сам начнёт защищать комбинаторику и проводить воспитательные беседы со своими друзьями.

Всего есть $n$ человек, пронумерованных от $1$ до $n$, Саша~--- имеет номер $1$. Некоторые пары людей дружат друг с другом. Человек под номером $i$ ($2 \le i \le n$) будет писать всем своим друзьям о своей нелюбви к комбинаторике в дни $a_i$, $a_i + t_i$, $a_i + 2t_i$ и так далее, пока не окажется, что кто-то из его друзей в этот день уже защищает комбинаторику. В этом случае с ним \textbf{в тот же день} проведут воспитательную беседу, и, \textbf{начиная со следующего дня}, он будет защищать комбинаторику. Саша защищает комбинаторику начиная со дня $1$.

Для каждого человека, кроме Саши, определите, в какой день с ним проведут воспитательную беседу.

\InputFile
Первая строка содержит два целых числа $n$ и $m$ ($2 \le n \le 100\,000$, $1 \le m \le 100\,000$)~--- количество людей, включая Сашу, и количество дружеских связей между людьми.

Вторая строка содержит $n - 1$ целых чисел $a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)~--- моменты времени, когда каждый из людей начинает писать своим друзьям.

Третья строка содержит $n - 1$ целых чисел $t_2, \dots, t_n$ ($1 \le t_i \le 10^9$)~--- периоды, с которыми каждый человек пишет своим друзьям.

В каждой из следующих $m$ строк содержится два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$)~--- номера дружащих людей.

Гарантируется, что пары дружащих людей не повторяются, то есть $(u_i, v_i) \ne (u_j, v_j)$ и $(u_i, v_i) \ne (v_j, u_j)$, если $i \ne j$.

Гарантируется, что в результате процесса, описанного в условии, с каждым человеком в конце концов проведут воспитательную беседу.

\OutputFile
В единственной строке выведите $n - 1$ чисел~--- номера дней, когда с человеком под номером $i$ ($2 \le i \le n$), проведут воспитательную беседу.

\Scoring
Тесты к этой задаче состоят из девяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. \textbf{Offline-проверка} означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования. Группы в данной задаче <<склеиваются>>. Это означает, что за подгруппу начисляются баллы, если хотя бы одна из ваших посылок успешно проходит все её тесты. Обратите внимание, что если у подгруппы имеются необходимые подгруппы, то для проверки на данной подгруппе текущая посылка должна пройти тесты во всех этих необходимых подгруппах (при этом результаты предыдущих посылок не учитываются).


\begin{center}
\begingroup
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
& & \multicolumn{2}{c|}{Доп. ограничения} & & \\
\cline{3-4}
\raisebox{2.25ex}[0cm][0cm]{Группа}
& \raisebox{2.25ex}[0cm][0cm]{Баллы}
& $n$, $m$ & $a_{i}$, $t$
& \raisebox{2.25ex}[0cm][0cm]{Необх. группы}
& \raisebox{2.25ex}[0cm][0cm]{Комментарий}
\\
\hline 
0 & 0 & -- & -- & -- & Тесты из условия \\ \hline 
1 &  6 & $n \le 10$ & -- & 0 & -- \\ \hline
2 &  7 & $m = n - 1$ & -- &  -- & -- \\ \hline
3 &  8 & -- & $a_i = t_i = 1$ & -- & -- \\ \hline
4 &  5 & -- & $t_i = 1$ & 3 & -- \\ \hline
5 & 11 & -- & $a_i, t_i \le 10$ & 0, 3 & -- \\ \hline
6 & 14 & $n, m \le 300$ & $a_i, t_i \le 300$ & 0 & --  \\ \hline
7 & 13 & $n, m \le 4000$ & $a_i, t_i \le 4000$ & 0, 6 & -- \\ \hline
8 & 15 & $n, m \le 4000$ & -- & 0, 6, 7 & -- \\ \hline
9 & 21 & -- & -- & 0--8 & \textbf{Offline-проверка} \\ \hline
\end{tabular}
\endgroup
\end{center}


\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\end{example}

\Note
В первом тестовом примере:

\begin{shortitems}
\item Человек $1$~--- это Саша.
\item Человек $2$ собирается писать своим друзьям, Саше и человеку $3$, в дни $3, 6, 9, \dots$.
\item Человек $3$ собирается писать своему другу, человеку $2$, в дни $2, 4, 6, \dots$.
\end{shortitems}

Процесс выглядит так:

\begin{shortitems}
\item В день $2$ человек $3$ пишет человеку $2$.
\begin{itemize}
\item Человек $2$ ещё не защищает комбинаторику, поэтому ничего не происходит.
\end{itemize}
\item В день $3$ человек $2$ пишет Саше и человеку $3$.
\begin{itemize}
\item Саша проводит со человеком $2$ воспитательную беседу.
\end{itemize}
\item В день $4$ человек $3$ снова пишет человеку $2$.
\begin{itemize}
\item Начиная со этого дня человек $2$ защищает комбинаторику, поэтому он проводит с человеком $3$ воспитательную беседу.
\end{itemize}
\end{shortitems}

\end{problem}

