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.