题目描述

竞选时，要求选民在n个候选人中选择，n个人的名字为 A,B,C,D……连续n个大写字母，如果选择n个人名字之外的人员，则为废票。 统计时以输入’#’为结束标记。请按候选人的得票数目从大到小顺序输出候选人的名字及得票情况。

输入格式

第一行 n 为候选人个数（ n<=26,因为候选人的名字全是1位大写字母） 第二行为一行大写字母，最后一个字符为'#'，每个大写字母代表一张选票，选票个数<=2000.

输出格式

n行，从选票个数从大到小输出每个候选人的名字和票数。

样例

input*

4  （有四个候选人，名字为 A B C D）
BBBBDDDCFADDCBBBAABBDDCFFE#

output

B:9
D:7
A:3
C:3

限制与提示

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$