I. Битва за Хогвартс

Замок окружён башнями. Защитный барьер строится по выпуклой оболочке башен; за минуту Тёмный Лорд разрушает барьер, и вместе с ним падают все башни, стоявшие на оболочке. После этого барьер мгновенно возводится заново по оставшимся башням, и всё повторяется, пока башни не кончатся.

Для каждой башни определите, на какой минуте она падёт.

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

В первой строке — число $n$ ($1 \le n \le 10^4$). В следующих $n$ строках — целые координаты башен ($|x|, |y| \le 10^4$).

Выведите $n$ строк: для каждой башни в порядке ввода — минуту, на которой она падёт.