题目描述

在一场选举过程中，$n$ 张选票依次打开，给定每张选票提名的候选者姓名，请统计在每打开一张选票后，谁是当下得票最高的候选者。

若两名候选者得票数量一样多，输出字典序排名靠前的候选者名字。

输入格式

• 第一行：单个整数：表示 $n$
• 第二行到第 $n+1$ 行：第 $i+1$ 行有一个字符串 $s_i$ 表示第 $i$ 张选票提名的候选人，保证 $s_i$ 只含英文字母。

输出格式

共 $n$ 行：在第 $i$ 行，输出第 $i$ 张选票打开后，最领先的候选人姓名。

4
Tom
Jerry
Tom
Jerry

Tom
Jerry
Tom
Jerry

数据范围

• $30\%$ 的数据，$1\leq n\leq 100$
• $60\%$ 的数据，$1\leq n\leq 50,000$
• $100\%$ 的数据，$1\leq n\leq 300,000$