Given StringTM#1769
Vasyl, an employee at the renowned European Institute of Advanced Studies, finally discovered a computer at his workplace. Not being very experienced with computers, he did not use all the capabilities of this mysterious device. However, from his school days, Vasyl remembers that programmers use something called variables. Not recalling exactly how to use them, he decided to apply one as follows:
Consider the given string s.
Select a string t.
Replace some non-overlapping occurrences of t in s with the variable A, which (surprisingly) is represented by the uppercase Latin letter 'A', obtaining string g.
Vasyl's goal is to minimize the total number of characters, that is, |\textbf{t}| + |\textbf{g}|.
The input consists of a single line containing the string s (1 \leq |\textbf{s}| \leq 10000). The string consists of lowercase Latin letters.
Output the optimal set: print t on the first line and g on the second line.
Example 1