Основные проблемы у Эдди и Венома появляются в тот момент, когда Карнаж со своим носителем сбегают из тюрьмы. Если бы тюрьма была более защищенной, ничего бы плохого не произошло, и все жили бы долго и счастливо.
Наученный опытом, новый начальник тюрьмы Сан Квентин постановил при ее восстановлении построить камеру особо строгого режима, которая будет представлять из себя комнату, расположенную внутри другой комнаты. Законы Сан-Франциско позволяют строить комнаты строго одного из $$$n$$$ типов, $$$i$$$-й тип представляет из себя прямоугольник со сторонами $$$a_i$$$ с запада на восток и $$$b_i$$$ с севера на юг (но не наоборот). Комнату $$$a_i \times b_i$$$ можно разместить внутри комнаты $$$a_j \times b_j$$$ тогда и только тогда, когда $$$a_i \leqslant a_j$$$ и $$$b_i \leqslant b_j$$$. В целях безопасности внешняя и внутренняя комнаты обязательно должны быть разных типов (но не обязательно разных размеров).
Разумеется, не для любых двух комнат верно, что одну можно разместить внутри другой. Например, комнаты размеров $$$4 \times 6$$$ и $$$5 \times 3$$$ не могут быть расположены одна внутри другой, так как $$$4 < 5$$$, но $$$6 > 3$$$. Поэтому, если начальнику тюрьмы принципиально захочется, чтобы внутренняя комната была именно $$$i$$$-го типа, и никакого другого, ему разрешено в качестве исключения выбрать любой тип $$$j \neq i$$$ и «расширить» комнату $$$a_j \times b_j$$$ до $$$a \times b$$$ (то есть выбрать произвольные $$$a \geqslant a_j$$$, $$$b \geqslant b_j$$$), заплатив правительству города $$$(a + b) - (a_j + b_j)$$$ денег, чтобы после этого внутри нее помещалась комната $$$i$$$-го типа.
Очевидно, начальник тюрьмы хочет потратить как меньше денег, но при этом не хочет рисковать безопасностью. Поэтому перед тем, как сделать окончательный выбор, он хочет оценить, сколько ему придется минимум заплатить правительству, если внутренняя комната будет типа $$$i$$$, для каждого $$$i$$$ от $$$1$$$ до $$$n$$$.
В первой строке ввода дано единственное целое число $$$n$$$ — количество типов комнат, официально разрешенных в Сан-Франциско ($$$2 \leqslant n \leqslant 2 \cdot 10^5$$$).
В $$$i$$$-й из следующих $$$n$$$ строк через пробел записаны целые числа $$$a_i$$$ и $$$b_i$$$ — размеры $$$i$$$-го типа комнаты ($$$1 \leqslant a_i, b_i \leqslant 10^9$$$). Не гарантируется, что все типы отвечают разным размерам комнат. Если есть два типа с одинаковыми размерами, комнаты этих типов можно размещать друг внутри друга.
Выведите через пробел $$$n$$$ целых чисел, $$$i$$$-е из которых равно минимальному количеству денег, которое придется заплатить, чтобы построить камеру строгого режима с внутренней комнатой $$$i$$$-го типа.
3 1 3 2 2 3 1
1 1 1
5 4 4 6 3 3 3 2 5 1 1
1 2 0 1 0