Given rowTM
Vasyl, an employee at the renowned Research Institute of Advanced Studies, has finally discovered a computer at his workplace. Although not very experienced, he recalls from his school days that programmers use something called variables. While he's unsure of their exact use, he decides to experiment with them as follows:
Start with a given string^TM s.
Select a specific string t.
Replace some non-overlapping occurrences of t in s with the variable A, represented by the capital letter 'A', to create a new string g.
Vasyl's objective is to minimize the total number of characters, i.e., |t| + |g|.
Input
The input consists of a single line containing the string^TM s (1 ≤ |s| ≤ 10000). The string is composed of lowercase Latin letters.
Output
Output the optimal solution: the first line should contain t, and the second line should contain g.