Description

Your university's teams are celebrating an outstanding performance at this year's NWERC in Karlsruhe. After a delicious dinner at a local restaurant, you call it a day. The trip home tomorrow will be a long one.

While trying to pay the bill, your group realizes that the restaurant takes no cash. Furthermore, it is too late to split the bill. Caught off-guard, everybody starts to open their wallets and puts some cash on the table. Someone has to pay the bill with their credit card and take the cash.

Each person $i$ spent $€b_i$ during the evening but has $€a_i$ in cash to contribute to the group payment (if someone else pays). To keep it fair, the group does not want the person who pays the final bill (and takes the money from the cash pool) to end up paying more than their individual share. Thus, if person $i$ is the one paying, then the remainder of the bill, after accounting for the cash contributions of the others, should not be more than their own share $€b_i$ of the bill.

Help the group determine who should pay the final bill.

Input Format

The input consists of:

• One line with an integer $n$ ($2 \le n \le 10^5$), the size of your dinner group.
• $n$ lines, the $i$th of which contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 1000$), the amount of cash person $i$ would contribute if someone else pays and their share of the bill, respectively.

Output Format

If there is no suitable person to settle the bill, output “impossible”. Otherwise, output one integer $i$ ($1 \le i \le n$), the index of the person settling the bill. If there are multiple valid solutions, you may output any one of them.

3
4 3
5 4
1 3

3

5
1 4
8 1
1 4
2 5
4 6

impossible

8
4 3
5 8
7 2
1 9
6 3
2 6
5 7
8 6

4

Hint

Explanation on Sample #2. The total bill is $€20$. If the first person settles the bill, they get $€15$ in cash from the others, paying $€5$ by themselves, which is more than their individual share of $4$. A similar reasoning for each of the other people shows that they would also pay more than their individual share, and thus, there is no suitable person to settle the bill.