Description

This game is played by two players, A and B, who take turns placing pieces on the grid intersection points of a $1000000\times1000000$ square chessboard. The coordinates of a grid intersection point are written as $(x,y)$, where $(0, 0)$ represents the point at the bottom-left corner of the board.

No two pieces may be placed on the same coordinate. Each time a new piece is added, the counter on the board automatically computes the number of unblocked squares that can be formed by the pieces currently on the board.

An unblocked square means a square defined by any two pieces such that the interior of the square contains no other pieces. After each move, the number of unblocked squares computed is the score obtained for placing that piece. Each player's total score is the sum of the scores for all pieces they have placed.

Write a program to compute the cumulative total scores of players A and B.

Input Format

The first line contains a single integer $n$, indicating that a total of $n$ pieces are placed in this game.

The next $n$ lines each contain two integers, in order, representing the positions where these $n$ pieces are placed.

Output Format

Output two integers, representing the cumulative scores of the two players in this game. A's score comes first, and B's score comes second, separated by a single space.

4      
2  3    
3  4    
1  2    
4  1   

2  6    

Hint

For $100\%$ of the testdata, $1\le n\le5000$, $0\le x,y\le 1,000,000$.

Translated by ChatGPT 5