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

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

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

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