Potential Victories in Byteland

In Byteland, every citizen is registered on two programming sites: CodeCoder and TopForces, each having its own unique rating system. Every citizen is assigned a unique integer rating on each site. Higher rating means better skill.

A Bytelandian citizen A is said to have a chance to beat citizen B in a programming competition if there exists a sequence of citizens $$A = P_{0}, P_{1}, \dots, P_{k} = B$$ (with \(k \ge 1\)) such that for every consecutive pair \(P_{i}\) and \(P_{i+1}\) (\(0 \le i r_{P_{i+1}} \quad \text{or} \quad s_{P_{i}} > s_{P_{i+1}},$$ where \(r_i\) is the CodeCoder rating and \(s_i\) is the TopForces rating of citizen \(i\).

Your task is: Given the ratings of \(n\) citizens, determine for each citizen the number of other citizens they can possibly beat (i.e. can reach through such a chain).

inputFormat

The first line contains a single integer \(n\) (the number of citizens). \(n\) lines follow, each containing two space-separated integers. The \(i\)-th line (1-indexed) contains \(r_i\) and \(s_i\), the CodeCoder rating and TopForces rating for the \(i\)-th citizen respectively.

It is guaranteed that in each rating system all ratings are unique.

outputFormat

Output \(n\) lines, where the \(i\)-th line contains a single integer denoting the number of other citizens that the \(i\)-th citizen can possibly beat.

sample

4
3 2
1 4
2 1
7 3

3
3
3
3