Основные проблемы у Эдди и Венома появляются в тот момент, когда Карнаж со своим носителем сбегают из тюрьмы. Если бы тюрьма была более защищенной, ничего бы плохого не произошло, и все жили бы долго и счастливо.
Наученный опытом, новый начальник тюрьмы Сан Квентин постановил при ее восстановлении построить камеру особо строгого режима, которая будет представлять из себя комнату, расположенную внутри другой комнаты. Законы Сан-Франциско позволяют строить комнаты строго одного из $$$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$$$ и $$$7 \times 1$$$ не могут быть расположены одна внутри другой. Поэтому начальнику разрешено выбрать любой тип внутренней комнаты $$$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 2 5 7 2 1 10
1 1 1 1 5