On a night out, Maged enters a bar and is looking for a beer. Maged's bank account is nearly empty, but he still wants to get some bang for his hard-earned bucks. When looking at the drinks list, Maged recalls seeing an Instagram Reel that told him that the cheapest item on the menu always has a high margin since so many people buy it, so the second-cheapest item is usually the best value.

Thus, Maged decides to go with the second-cheapest beer on the menu. However, for some reason, the menu items are in random order, so he wants you to figure out which beer that is for him.

Follow-up: Once you have solved this, think about if your solution could generalise to the 3rd cheapest, or 4th cheapest, or ~k~th cheapest element. You don't have to solve this, but we can discuss this after.

Input

The first line consists of an integer ~n\ (2 \leq n \leq 10^6)~ representing how many items there are on the menu.

The following ~n~ lines each consist of an integer and a string seperated by a space, representing the price and name of each item. The prices have ~(1 \leq x \leq 10^3)~ and the name strings have ~(1 \leq \text{S.length} \leq 10)~ with only lowercase and uppercase English characters and numbers.

Output

Output the name of the second-cheapest item. If there is a tie, output the one that appeared first on the list. It is guaranteed that there will be a second-cheapest item (i.e. there won't be any inputs where every item has the same price).

Your solution must run in linear time - ~O(n)~ - or faster.

Example

Input 1

4
10 CoopersPaleAle
8 CarltonDry
11 XXXXGold
15 GreatNorthernLager

Output 1

CoopersPaleAle

Explanation 1

The cheapest item is CarltonDry with a price of 8. After that, the next cheapest (second cheapest) item is CoopersPaleAle with a price of 10.

Input 2

4
1 FailAle
1 JPA
2 Pacific
2 Beer3

Output 2

JPA

Explanation 2

This behaviour is not too obvious, since there are ties for both prices 1 and 2. Since FailAle is first, it is the minimum element. Thus, JPA is the second minimum element since it appears after. If JPA didn't exist in the input, then the output would be Pacific as it occurs before Beer3 even though they cost the same.