«Welcome to the glorious city of Praven, the capital of the Kingdom of Swadia and simply the best place in all of Calradia!» — loudly proclaims the man dressed in luxurious silk at the entrance to King Harlaus’ fortress. It’s no wonder — a successful military campaign against the Khergit Khanate has greatly enriched the kingdom, and to celebrate, it has been decided to hold a knightly tournament to determine the best warrior on the entire continent.
Approaching the list of participants, you see that n
people have signed up for the tournament. You know about each of them, what weapon they are equipped with, and you also know from reliable rumors about the wealth of each of them. Next to the list are the rules of the tournament. They state the following:
- Each of the knights will engage in a one-on-one combat with spears and shields against each other.
- A knight is «crushed» in battle if the strength of his shield does not exceed the attack of the opponent’s spear.
- A knight wins the battle if his opponent was «crushed» and he himself was not.
- A knight is declared the «absolute winner» of the tournament if he defeats all opponents.
You know for a fact that each knight is very eager to become the «absolute winner», so they are willing to invest all their money in improving their equipment. Fortunately, right now, to increase the power of the spear or increase the strength of the shield by one unit, only one gold coin is needed, and the knights have accumulated mountains of them after the successful war.
You are only interested in one question — is there a knight who can become the «absolute winner» with the right equipment regardless of the actions of others, as then you can make a good bet. Keep in mind that before the duel, the knights do not know how their opponents are preparing.
The first line contains a single integer n — the number of knights participating in the tournament (1 ≤ n ≤ 105).
The next n lines contain a triplet of integers ai, di, gi — the attack strength of the spear, the strength of the shield, and the number of gold coins of the i-th knight (0 ≤ ai, di, gi ≤ 109).
In a single line, output the number i — the number of the knight who is the absolute winner of the tournament. If there is no such knight, output -1. The knights are numbered from 1 to n in the order they are described in the input data.
100 4 5
1 2 8
5 2 2
4 1 10
10 4 0
In the first example, knight number 1 cannot win. Even if he invests all his money in defense, it will be equal to 9, and the second knight can also improve his attack to 9. In this case, the first knight is «crushed» despite the fact that his opponent is too.
Problem Author: Aleksey Bykov
Problem Source: Ural School Programming Contest 2021