You are staying at point \((1,\ 1)\) in a matrix \(10^9 \times 10^9\). You can travel by following these steps:

If the row where you are staying has 1 or more apples, then you can go to another end of the row and can go up.
Otherwise, you can go up.

The matrix contains \(N\) apples. The \(i^{th}\) apple is at point \((x_i,\ y_i)\). You can eat these apples while traveling.

For each of the apples, your task is to determine the number of apples that have been eaten before.

Input format

The first line contains a single integer \(N\) \((1 \le N \le 10^5)\) denoting the number of apples.
The next \(N\) lines contain two integers\(x_i,\ y_i\) \((1 \le x_i,\ y_i \le 10^9)\) denoting the coordinates of the \(i^{th}\) apple.

Output format

Print \(N\) lines containing a single integer.