Compressor P77072

You are working in a program to compress text files. Write a function that finds the longest repeated subsequence in a a fragment of text, such that the two appearances of the subsequence do not overlap. Your program distinguishes uppercase and lowercase letters. If there are more than an option to choose of subsequence, choose that onse that happens before in the text.

For instance, given the sequence “ABCDABCFG”, the longest repeated appearance “ABC”. In the sequence “ABABA”, “AB” as well as “BA” are repeated subsequences, so that we choose “AB” because it appears first. (Although “ABA” appears twice as subsequence, the two appearances have a letter in common and they cannot we used.)

Input

The input contains various lines. Each line contains a text to consider. Each text contains between 1 and 50 characters between ’A’-’Z’, ’a’-’z’, ’0’-’9’ and ’ ’. (Hint: getline(cin,s) reads a whole line of text and stores it in the variable of string type s.)

Output

For each text of the input, a line containing the longest repeated subsequence. If any subsequence is repeated, it must print a line in white.