Hardutta is planning an inter college football league. He has invited n teams, including our own team from BPHC. Now, one of the organizers Ramehta was hell bent on knowing one thing : How many matches will all the teams play in their home kit and how many matches will they play in their away kit? A little backstory on Ramehta, he is an Arsenal fan and pretty much annoys the hell out of everybody with his facebook commenting. So Hardutta wants your help to stop Ramehta from annoying him by providing the answer.

The kit for home games of the i-th team has color xi and the kit for away games of this team has color yi (x_i<=y_i). In the tournament, each team plays exactly one home game and exactly one away game with each other team. The team, that plays the home game, traditionally plays in its home kit. The team that plays an away game plays in its away kit. However, if two teams has the kits of the same color, they cannot be distinguished. In this case the away team plays in its home kit.

Input

The first line contains a single integer n (2<=n<=10⁵) — the number of teams. Next n lines contain the description of the teams. The i-th line contains two space-separated numbers xi, yi (1<=x_i,y_i<=10⁵; x_i and y_i are not equal) — the color numbers for the home and away kits of the i-th team.

Output

For each team, print on a line the number of games this team is going to play in home and away kits, correspondingly, separated by spaces. Print the answers for the teams in the order they appeared in the input.