描述

小块在开放日听的是"向量数据库与Embedding"讲座。他了解到，在AI系统中，向量数据库是一种存储和检索数据的方式。比如，当我们向AI提问时，系统会把问题转换成一段"向量"，然后在向量数据库中查找与它最相似的内容。

给定n个关键词（仅包含小写字母），统计每个关键词出现的次数，然后按以下规则排序后输出：

1. 出现次数多的排在前面
2. 出现次数相同时，按关键词的字典序（字母顺序）排列

输入输出格式

输入

第一行一个正整数n（1≤n≤1000） 第二行n个关键词，单词之间以空格分隔

输出

若干行，每行输出一个"关键词:次数"，按题目要求的顺序排列

样例

6
apple banana apple orange banana apple

apple:3
banana:2
orange:1