Innvolsarinnihaldslýsing

Image by Randall Munroe, xkcd.com

Ingfríður has grown curious about her internal content description. She heard that various properties of an individual can be deduced from these data, so she has to try it. After getting the data sent over from the company Encode she has everything she needs. To analyse the data she needs to find sections that match known patterns, but if analysing some sections is good, analysing all sections must be better. Thus Ingfríður wants to analyse all sections. We define a section to be all characters in the data from some specific starting character to some ending character.

Input

The input contains a single line giving the internal content description of Ingfríður. The description consists of the letters A, C, G and T and has no spaces. The description is at most $100$ letters in length.

Output

For each section in the description print one line, the number of occurrences it has in the description and then the section itself, separated by spaces. A section should not be printed multiple times in the output even if it occurs multiple times. The lines should be printed in descending order by the number of occurrences. If two sections are tied for number of occurrences, resolve the tie by putting the section that comes first alphabetically before the other.

ACGT

1 A
1 AC
1 ACG
1 ACGT
1 C
1 CG
1 CGT
1 G
1 GT
1 T

AGAGA

3 A
2 AG
2 AGA
2 G
2 GA
1 AGAG
1 AGAGA
1 GAG
1 GAGA

GATTACA

3 A
2 T
1 AC
1 ACA
1 AT
1 ATT
1 ATTA
1 ATTAC
1 ATTACA
1 C
1 CA
1 G
1 GA
1 GAT
1 GATT
1 GATTA
1 GATTAC
1 GATTACA
1 TA
1 TAC
1 TACA
1 TT
1 TTA
1 TTAC
1 TTACA