Willson the Canada Goose is like any other Canada Goose - he can sometimes become upset with other geese (or humans) and begin to fight them. However, geese will never fight with their mates.

After migrating back from California, Willson's extended family, consisting of ~2N~ geese, are grazing in a field. The ~i^{th}~ goose is located at ~(x_i,y_i)~, and no two geese will share the same location. Define the distance between the ~p^{th}~ goose and the ~q^{th}~ goose to be ~\text{dist}(p,q) = |x_p-x_q|+|y_p-y_q|~, that is, the Manhattan distance.

For ~1 \le k \le N~, the ~(2k-1)^{th}~ and ~(2k)^{th}~ geese are mates. Suppose two geese ~p~ and ~q~ are mates. Then for any other goose ~r~, goose ~p~ will honk at goose ~r~ if ~\text{dist}(p,r) < \text{dist}(p,q)~. Similarly, goose ~q~ will honk at goose ~r~ if ~\text{dist}(q,r) < \text{dist}(p,q)~.

If two geese honk at each other, then they will fight once. Can you determine the number of fights that each goose will get into?

Constraints

For all subtasks:

~1 \le N \le 60\,000~

All coordinates ~c~ satisfy ~1 \le c \le 60\,000~.

No two geese will share the same location.

Subtask	Points	Additional constraints
~1~	~15~	~N \le 2\,000~
~2~	~45~	~1 \le c \le 1\,000~
~3~	~40~	No additional constraints.

Input Specification

The first line of input will contain ~N~.

~2N~ lines of input follow. The ~i^{th}~ line will contain integers ~x_i, y_i~.

Output Specification

Output ~2N~ lines. On the ~i^{th}~ line, output the number of fights that goose ~i~ will get into.

Sample Input

4
1 1
3 1
4 1
6 1
1 21
1 23
1 24
1 25

Sample Output

0
1
1
0
0
0
0
0

Explanation for Sample Output

Goose ~2~ and goose ~3~ will honk at each other, so they fight. Note that goose ~7~ does not honk at goose ~6~, so these two geese do not fight.