Adriatic

"The land of a thousand islands" was an official motto of Croatian tourism in the mid 1990s. The motto is not exact, because Croatia has a little more than 1000 islands, but island hopping, sailing from one island to the next, really is a popular summer activity.

In this task the map of the Adriatic sea is a grid of unit squares with 2500 rows and 2500 columns. Rows are numbered 1 through 2500 from north to south, and columns are numbered 1 through 2500 from west to east. There are $N$ islands in the sea, numbered 1 through $N$, and each island lies inside one unit square. The location of island $K$ is given by the row number $R_K$ and the column number $C_K$ of that square. No two islands lie in the same square.

Because of the winds and the sea currents, a boat can sail directly from an island only to the islands that lie northwest or southeast of it. Precisely, it is possible to sail from island $A$ to island $B$ in one hop if $R_A < R_B$ and $C_A < C_B$, or if $R_A > R_B$ and $C_A > C_B$. Neither the distance between the two islands nor the presence of other islands between them changes this. When a direct hop from $A$ to $B$ is impossible, a sequence of hops through other islands can still connect them. The sailing distance from $A$ to $B$ is the smallest number of hops needed to sail from $A$ to $B$.

For example, in the first example below, the island in row 2, column 3 reaches four islands in a single hop, and the sailing distance to each of the two remaining islands is 2.

A sailing congress is being planned and the organizers consider every island as a possible location. For a candidate island they want to know this: if every other island sends one sailboat, what is the smallest total number of hops the sailboats need in order to all reach the candidate island? That total is the sum of the sailing distances from all other islands to the candidate island. Given the locations of the $N$ islands, compute for every island $K$ the sum of the sailing distances from all other islands to island $K$.

The input is such that for all islands $A$ and $B$ it is possible to sail from $A$ to $B$ using some sequence of hops.

The first line contains an integer $N$ ($3 \le N \le 250\,000$), the number of islands. Each of the next $N$ lines contains the location of one island: two integers between 1 and 2500 inclusive, the row number and the column number.

Print $N$ lines. For each island, in the order the islands are given in the input, print on its own line the sum of the sailing distances from all other islands to that island.