在之前的一场比赛中，参赛者需要解决一个简单的问题。他们会得到一个字符串，并需要打印出其中每一个唯一的子串，以及该子串在原字符串中出现的次数。例如，AB 会打印 A 1 B 1 AB 1，而 AAA 会打印 A 3 AA 2 AAA 1。

在将此题复制到本次比赛中重复使用时，出现了一些错误。输入数据范围发生了巨大变化，使得该问题变得完全不可能解决！幸运的是，输出校验器也出现了混乱，这在一定程度上抵消了上述影响。现在，它不再检查绝对正确性，而仅要求输出中每个字符出现的次数正确即可。通过对输出应用游程编码（run length encoding）进行快速修复，该问题终于再次变得可解，比赛也能按计划继续进行。对吧？

图片来自 commons.wikimedia.org。

输入格式

输入包含一个长度至少为 1 且最多为 $10^6$ 的字符串。它仅包含 ASCII 大小写字母。该字符串后紧跟一个换行符。

输出格式

对于在上述问题描述的输出中出现次数不为零的每个非空白字符，请将其与它的出现次数打印在同一行，并用空格分隔。请按 ASCII 字符值的升序打印这些行。

样例

输入格式 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