题目描述

在之前的一场比赛中，参赛者需要解决一个简单问题：给定一个字符串，输出它的每个不同子串，以及该子串在原字符串中出现的次数。

例如：

• 对字符串 AB，原问题会输出 A 1 B 1 AB 1；
• 对字符串 AAA，原问题会输出 A 3 AA 2 AAA 1。

后来这个问题被复制到本场比赛中复用，但出现了好几个错误：输入范围被大幅增大，使原问题几乎不可能完成。幸运的是，输出校验器也被弄坏了。现在它不再要求完整输出正确，而只要求输出文本中每个字符出现次数正确。

再加上一个“热修复”：输出会经过游程编码。这样问题终于又变得可解了——真的如此吗？

输入格式

输入包含一个字符串 $S$，其长度至少为 $1$，至多为 $10^6$。

字符串只包含 ASCII 大写字母和小写字母。字符串后跟一个换行符。

输出格式

考虑原问题的输出内容。对于其中出现次数非零的每个非空白字符，输出该字符以及它在原输出中出现的次数，中间用一个空格分隔。

输出行应按字符的 ASCII 码升序排列。

数据范围

• $1 \le |S| \le 10^6$
• $S$ 仅包含 ASCII 大写字母 A 到 Z 和小写字母 a 到 z

样例

输入 #1

ABC

输出 #1

1 6
A 3
B 4
C 3

输入 #2

aaaab

输出 #2

1 6
2 1
3 1
4 1
a 20
b 5