Chain Reaction in Falling Trees

You are given N trees, each located at a distinct point in the 2D plane. Each tree has coordinates \( (x_i, y_i) \). When you push a tree, it may cause a chain reaction: if there is a tree to its right (i.e. with a greater \( x \)-coordinate) that shares the same \( y \)-coordinate, then that tree will also fall. Moreover, the falling of that tree can trigger the fall of another tree further to the right with the same \( y \)-coordinate, and so on.

Formally, after sorting the trees in increasing order of \( x \), for each tree \( i \) (in sorted order), if there exists a tree \( j \) with \( j > i \) such that \( y_j = y_i \), then the number of trees hit by tree \( i \) is defined as:

[ \text{hits}_i = 1 + \text{hits}_j ]

If no such tree exists, then \( \text{hits}_i = 0 \). Your task is to compute for each tree (in the original input order) the total number of trees that will be hit if that tree is pushed, considering the chain reaction described above.

inputFormat

The input is given from stdin in the following format:

• The first line contains an integer \( N \) representing the number of trees.
• The following \( N \) lines each contain two integers \( x_i \) and \( y_i \), the coordinates of the \( i\)-th tree.

Note that the trees are not necessarily given in sorted order.

outputFormat

Output a single line to stdout with \( N \) integers separated by a single space. The \( i\)-th integer should be the number of trees that are hit due to the chain reaction when pushing the \( i\)-th tree (in the original input order).

5
1 1
2 2
3 3
4 4
5 5

0 0 0 0 0