题目描述

在一次激动人心的海盗探险中，你发现了一张古老的藏宝图，上面刻有一串神秘的符号："A", "C", "G", "T"，它们代表了不同的方向。传说，重复的符号序列指向隐藏宝藏的秘密路径。作为聪明的小探险家，你的任务是找出这串符号中所有出现次数超过一次的序列，并计算它们的确切出现次数。

给定一个只包含字符 'A', 'C', 'G', 'T' 的字符串（代表方向指令，长度在1到100之间），确定哪些指令序列出现了至少两次，并计算这些序列的出现次数。

输入格式

输入包含一行，一个由字符 'A', 'C', 'G', 'T' 组成的字符串，表示藏宝图上的指令。

输出格式

输出所有出现次数超过一次的指令序列及其出现次数，每个输出项包括指令序列和次数，中间用单个空格隔开。按指令序列的字典序从小到大依次输出，每行一个。

示例

输入

TAGGTAGG

输出

A 2
AG 2
AGG 2
G 4
GG 2
T 2
TA 2
TAG 2
TAGG 2

解释

在这个例子中，'G' 指令出现了4次，表明向这个方向走可能是找到宝藏的关键。其他如 'TAG' 和 'AGG' 等指令序列也重复出现，可能代表了一条通往宝藏的复杂路径。