You are tasked with building a high-security prison cell, which should consist of a room located inside another room. The laws allow for the construction of rooms of strictly one of $$$n$$$ types, where the $$$i$$$-th type is a rectangle with dimensions $$$a_i$$$ from west to east and $$$b_i$$$ from north to south (but not vice versa). A room of size $$$a_i \times b_i$$$ can be placed inside a room of size $$$a_j \times b_j$$$ if and only if $$$a_i \leq a_j$$$ and $$$b_i \leq b_j$$$. For safety reasons, the outer and inner rooms must be of different types (but not necessarily different sizes).

Of course, it is not true for any two rooms that one can fit inside the other. For example, rooms of sizes $$$4 \times 6$$$ and $$$5 \times 3$$$ cannot be placed one inside the other, as $$$4 \lt 5$$$, but $$$6 \gt 3$$$. Therefore, if the warden insists that the inner room must be of type $$$i$$$ and no other, you are allowed to make an exception and choose any type $$$j \neq i$$$ and "expand" the room $$$a_j \times b_j$$$ to $$$a \times b$$$ to make it an outer room (that is, choose arbitrary $$$a \geq a_j$$$, $$$b \geq b_j$$$) paying the fee of $$$(a + b) - (a_j + b_j)$$$ in order for the room of type $$$i$$$ to fit inside it.

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