Description

Country H is carrying out a reclamation island project what is ongoing N weeks. The entire engineering sea area can be viewed as a grid of 1000x1000.

Every week there is a piece of 1x1 unit of the sea is filled into land. If we think that some pieces connect into a land as the island.(a piece can connect with its up, down, left, right these 4 pieces). Country H wants to monitor the number of islands of this sea, and wants to know the total area and the total perimeter of these islands.

For example, if project is ongoing 3 weeks. The first week we fill the piece (0, 0), so after the first week we can know that the number of islands is 1, total area is 1 and total perimeter is 4:

#..

...

...

The second week we fill the piece (1, 1), so after the second week we can know that the number of islands is 2, total area is 2 and total perimeter is 8:

#..

.#.

...

The last week we fill the piece (1, 0), so after the last week we can know that the number of islands is 1, total area is 3 and total perimeter is 8:

#..

##.

...

Can you help country H to solve this problem?

Format

Input

The first line contains one number $N$, means $N$ weeks of the project.$(1 \leq N \leq 100000)$

And then $N$ lines, each line contains two numbers $X$ and $Y$, means the coordinate of the sea area what will be filled in corresponding week.

Output

The output contains $N$ lines.
Each line contains 3 numbers, the number of islands, the total area and the total perimeter.

Samples

3  
0 0   
1 1   
1 0

1 1 4  
2 2 8  
1 3 8