No two letters should have a common point. As well as the general dash

Guide for telegraphists

The director of the Institute of Segments Geometry (ISG) invited Aaz to his office. According to the surroundings, the institution was not in poverty. But the problem at this time was different.

We are not out of work. Each time after the start of the season in the programming championship, we solve a lot of problems about the intersection of two segments on request of competition organizers. But it is still routine, and employees begin to lose interest. In some places, even instead of work some are involved in amateur - they organize concerts for accordion by candlelight. Can you formulate the problem for us, other than this, but not very far from it for the formulation of a bygone.

For example... Given n segments on a line. For each segment find the number of other segments that have with it at least one common point.

ISG staff enthusiastically took up the task. Moreover - they instructed you to write a program to solve it.

Input

Contains multiple test cases. First line of each test case contains the number of segments n (1 ≤ n ≤ 105). Each of the next n lines describes the segments: i-th line contains pair of integers Li and Ri - the start and end coordinates of i-th segment (-109 ≤ Li ≤ Ri ≤ 109). The total sum of values n in input does not exceed 105. Input data terminates with zero. The number of test cases is no more than 104.

Output

For each test print in one line n numbers as shown in sample: i-th line is the number of segments with which the i-th segment has at least one common point, not counting itself. Follow the output format as closely as possible.