小雏鸟正在整理一篇文章，他想知道每个单词出现了多少次。

现在给你 n 个单词，请你按 字典序 输出每个单词及其出现次数。

输入格式

第一行输入一个整数 $n (1 \le n \le 10^5)$，表示单词数量。

接下来 $n$ 行，每行输入一个只包含小写英文字母的字符串 $s (1 \le |s| \le 20)$。

输出格式

按字典序从小到大输出所有出现过的单词。

每行输出两个内容： 单词 和 它出现的次数，中间用一个空格隔开。

样例输入

7
apple
banana
apple
orange
banana
apple
grape

样例输出

apple 3
banana 2
grape 1
orange 1