Highest Selling Products

You are given several datasets representing the sales of different products over multiple days. Each dataset corresponds to a day. Each dataset begins with a positive integer (as a string) which indicates the start of the dataset, followed by that many lines, each containing a product ID and the number of units sold. A new dataset always starts with a digit line. The end of the input is marked by a line with a single 0.

Your task is to determine the product ID with the highest number of units sold for each day. In case of a tie, choose the product that appears first in the dataset.

Mathematically, if for a given day the dataset is \(\{(p_i, u_i)\}_{i=1}^{n}\), you are to find \(p_k\) such that \(u_k = \max_{1 \le i \le n} u_i\) and in the case of multiple indices with equal \(u_i\), select the one with the smallest index.

inputFormat

The input is given from stdin as follows:

• Several lines representing one or more datasets.
• A line containing a positive integer (e.g. 3) indicates the beginning of a new dataset.
• The following lines (until the next digit) contain a product ID (string) and the number of units sold (integer), separated by a space.
• The input terminates when a line with 0 is encountered.

outputFormat

For each dataset (day), output the product ID of the highest selling product on a separate line to stdout.

## sample

3
A123 300
B456 500
C789 200
2
P12 150
Q34 150
0

B456
P12

</p>