Secure Prison (Basic)

Eddie and Venom's troubles begin 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 experience, the new warden of San Quentin decided that the restored prison will include a maximum security cell, a room placed inside another room. San Francisco law allows rooms of exactly one of $n$ types. The $i$-th type is a rectangle with side $a_i$ from west to east and side $b_i$ from north to south (but not the other way around). A room $a_i \times b_i$ can be placed inside a room $a_j \times b_j$ if and only if $a_i \leqslant a_j$ and $b_i \leqslant b_j$. For safety, the outer and inner rooms must be of different types.

Unfortunately, none of the allowed room types fits inside another. For example, no two rooms of sizes $4 \times 6$, $5 \times 3$, and $7 \times 1$ can be placed one inside the other. So the warden may choose any type $i$ for the inner room and bend the rules a little for the outer room. He may choose any type $j \neq i$ for the outer room and expand the $a_j \times b_j$ room to $a \times b$ (that is, choose any $a \geqslant a_j$, $b \geqslant b_j$), paying the city government $(a + b) - (a_j + b_j)$ money, so that the room of type $i$ fits inside it.

The warden wants to spend as little money as possible without risking safety. So before making the final choice, he wants to know the minimum amount he must pay the government for each $i$ from $1$ to $n$, if the inner room is of type $i$.

The first line contains a single integer $n$, the number of room types officially allowed in San Francisco ($2 \leqslant n \leqslant 2 \cdot 10^5$). The $i$-th of the next $n$ lines contains integers $a_i$ and $b_i$ separated by a space, the dimensions of the $i$-th room type ($1 \leqslant a_i, b_i \leqslant 10^9$). It is guaranteed that no two different room types can be placed one inside the other.

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