Description

给定一个ASCII字符串（不包含\0,\n），统计它内部所有出现过的ASCII字符以及出现次数 。

Input

每一行一个ASCII字符串（长度不超过500000） 。

Output

输出它内部所有出现过的ASCII字符以及出现次数，按出现次数的降序排列。出现次数相同时按字符的ASCII码值从小到大排。出现次数多于1时，每个字符及次数单独一行，格式参照Sample Output。而所有出现只有1次的字符放在同一行上，两个字符之间空格隔开，最后一个字符后面直接回车结束，此时的次数不用出现。每组测试数据输完输一个空行。

Sample Input

aabcdddA

Sample Output

d *3
a *2
A b c

HINT

Source

NBU OJ cx19860824