111020 - 给朋友排序

每个人都会有N个朋友,每个人的名字都由“姓”和“名”两部分组成。你需要把他们按照姓的“流行程度”(即拥有该姓的朋友人数)从大到小排序,姓的流行程度相同的朋友按照他们在原始名单中出现的顺序排序。

Input

输入排序前的原始序列,每行包含一个朋友的姓和名(以空格间隔),朋友数不超过50000,每行为3~50个字符,且只包含大写字母和一个空格(行首行末无空格)。

Output

输出排序后的序列,每行包括一个朋友的姓和名,中间用一个空格隔开。

Examples

Input

ZHANG SAN
LI SI
WANG WU
WANG LIU
WANG QI
ZHANG WU
LI WU

Output

WANG WU
WANG LIU
WANG QI
ZHANG SAN
LI SI
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题