D. Guessing Game
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice and Bobo are engaged in an intriguing game, and you have the honor of being the judge.

In the $$$k$$$-th round, you will write down a pair of integers $$$(a_k, b_k)$$$ on the blackboard, clearly visible to both Alice and Bobo. Once they see the numbers, you will secretly select an integer $$$1 \leq i \leq k$$$, giving $$$a_i$$$ to Alice and $$$b_i$$$ to Bobo. The excitement builds as Alice and Bobo take turns either claiming they know the other's number or admitting that they do not know the answer, starting with Alice. The player who correctly guesses the other's number first will win the game!

Both players are exceptionally smart and honest, making the game all the more captivating. As you observe their interactions, you can't help but wonder: in the $$$k$$$-th round, how many values of $$$i$$$ that Alice wins, and how many values of $$$i$$$ that Bobo wins?

Input

The first line contains a single integer $$$q$$$ ($$$1 \le q \le 10^6$$$), denoting the total number of integer pairs.

Each of the following $$$q$$$ lines contains a single pair of integers $$$(a_k,b_k)$$$ ($$$1 \le a_k, b_k \le 10^5$$$).

It is guaranteed that $$$(a_1,b_1), (a_2,b_2),\ldots,(a_q,b_q)$$$ are distinct.

Output

Output $$$q$$$ lines. In the $$$k$$$-th line, output two integers $$$A_k$$$ and $$$B_k$$$, denoting the number of $$$i$$$ that Alice wins and Bobo wins respectively.

Example
Input
4
1 1
1 2
2 1
2 2
Output
1 0
0 2
1 2
0 0