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

1. 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.
2. 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.