Secure Prison

Eddie and Venom run into trouble when Carnage escapes from prison together with his host. If the prison had been more secure, nothing bad would have happened, and everyone would have lived happily ever after.

Learning from this, the new warden of San Quentin decided that the rebuilt prison will include a maximum security cell, a room placed inside another room. San Francisco law allows building rooms of exactly one of $n$ types. Type $i$ is a rectangle with side $a_i$ from west to east and side $b_i$ from north to south (and not the other way around).

Room $a_i \times b_i$ can be placed inside room $a_j \times b_j$ if and only if $a_i \le a_j$ and $b_i \le b_j$. For safety, the outer room and the inner room must be of different types (but they do not have to be different sizes).

Of course, not every pair of rooms fits one inside the other. For example, rooms of size $4 \times 6$ and $5 \times 3$ cannot be placed one inside the other, because $4 < 5$ but $6 > 3$. So if the warden wants the inner room to be of type $i$ and no other type, he is allowed to make an exception: he picks any type $j \ne i$ and expands room $a_j \times b_j$ to $a \times b$ (that is, picks any $a \ge a_j$ and $b \ge b_j$). He pays the city government $(a + b) - (a_j + b_j)$ money, so that a room of type $i$ fits inside it.

The warden wants to spend as little money as possible, but he does not want to risk safety. So before making the final choice, he wants to know the minimum amount he would have to pay the government if the inner room is of type $i$, for each $i$ from $1$ to $n$.

The first line contains a single integer $n$, the number of room types officially allowed in San Francisco ($2 \le n \le 2 \cdot 10^5$).

Each of the next $n$ lines contains two space-separated integers $a_i$ and $b_i$, the dimensions of room type $i$ ($1 \le a_i, b_i \le 10^9$). The sizes of the types are not guaranteed to be distinct. If two types have the same dimensions, rooms of these types can be placed inside each other.

Print $n$ integers separated by spaces. The $i$-th integer is the minimum amount of money that must be paid to build a maximum security cell whose inner room is of type $i$.