F. Football Forecast
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
CC BY 2.0 by Djuradj Vujcic on Wikimedia Commons

You would like to forecast the winner of the FIFA World Cup. This championship works in the following way:

First, there is group phase. In this phase, all participating teams are divided into groups of four in the order given in the input, and every pair of teams in such a group plays exactly one match. The winner scores $$$3$$$ points, the loser $$$0$$$ points. (For simplicity, we ignore the possibility of ties.) After the group phase, the two teams of each group with the most points proceed to the elimination phase.

In the elimination phase, matches are played according to a tournament bracket, which is a complete, rooted binary tree. The deepest layer of the tree has as many head-to-head matches as the number of groups. The teams ranked first in each group are assigned to these matches in the order given in the input, such that each match has one group winner. The teams ranked second in each group are then assigned to these matches in reverse order. For each match in this bracket, the loser is eliminated and the winner proceeds to the next layer in the bracket (ties are impossible here). The team winning the final match is declared World Champion.

Every team has a (unique) quality score, indicating how good it is. For simplicity, you assume that every match is won by the team with the higher quality score.

Given the quality score of every team and the complete structure of the tournament, determine who will win the World Cup.

Input

The input consists of:

  • One line with an integer $$$n$$$ ($$$4\leq n\leq {1024}$$$, $$$n$$$ is a power of $$$2$$$), the number of teams.
  • $$$n$$$ lines, each with a string $$$t$$$ and an integer $$$q$$$ ($$$1 \leq |t| \leq {20}$$$, $$$1\leq q\leq {10^6}$$$), the name of the team and its quality score.
The team names only consist of English lowercase letters (a-z).

The team names are pairwise distinct. The quality scores of the teams are pairwise distinct.

Output

Output the name of the team that will win the World Cup.

Examples
Input
4
netherlands 42
japan 31
sweden 24
tunisia 8
Output
netherlands
Input
8
australia 1337
kazakhstan 42
argentina 173205
belgium 314159
luxembourg 271828
canada 141421
antarctica 1
morocco 161803
Output
belgium