Gasoline Production

Interview

Time limit2sMemory limit1024 MB

Summary

Given n bids with line cost A, per-ton cost B, and price C, find the bid index that minimizes A/(C-B), with ties going to the smallest index.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Nanoneft is holding a tender to equip a new gasoline plant. Suppliers submitted $n$ bids for production lines. Each bid gives three integers:

$A_i$ : the cost of the production line;
$B_i$ : the cost of producing one ton of gasoline on this line;
$C_i$ : the price per ton that customers are willing to pay for gasoline produced on this line.

The break-even point is the amount of gasoline that must be produced on the line so that its total sale price equals the line cost plus the production cost. In other words, the break-even amount $x$ satisfies $x \cdot C_i = A_i + x \cdot B_i$ , so $x = \frac{A_i}{C_i - B_i}$ .

You are the acting manager of Nanoneft and must pick one bid. Choose the bid for which the break-even point requires the smallest amount of gasoline.

Input

The first line contains $n$ ( $1 \le n \le 10^5$ ), the number of bids. Each of the next $n$ lines contains three integers $A_i$ , $B_i$ , $C_i$ ( $1 \le A_i, B_i, C_i \le 10^9$ , $B_i < C_i$ ).

Output

Print the number of the bid with the smallest break-even point. If several bids are optimal, print the smallest number among them.

Examples2

Example 1
Input
```
2
1 2 3
2 1 3
```
Expected output
```
1
```
Example 2
Input
```
3
1 2 4
3 1 4
2 2 4
```
Expected output
```
1
```