KINA Is Not Abbreviation

When introducing new terms made up of several words, abbreviations are handy. An abbreviation is a word formed from the first letters of several consecutive words.

An abbreviation is called unambiguous when both of the following hold:

• it corresponds to exactly one sequence of words in the text (though that sequence may occur in the text more than once);
• it does not occur in the text on its own.

For example, in the text A recursive acronym KINA means "KINA is not abbreviation", the strings ARA and K are unambiguous abbreviations, the strings A and KINA are ambiguous abbreviations, and the strings RAA and KNA are not abbreviations at all.

To introduce an abbreviation, write it in parentheses immediately after the sequence of words it stands for; later occurrences of that same sequence of words may then be replaced by the abbreviation. In the text above, introducing the abbreviation K produces A recursive acronym KINA (K) means "K is not abbreviation".

If two occurrences of a sequence of words overlap, only one of them may be replaced by the abbreviation. Words in a sequence are separated by one or more non-alphabetic characters, and letters are compared case-insensitively. For instance, i18n is an occurrence of the word sequence I n.

The effectiveness of an abbreviation is the reduction in the number of letters after it is introduced. Only letters are counted; spaces, parentheses, and every other non-alphabetic character are ignored.

Given a text, find an unambiguous abbreviation whose effectiveness is as large as possible.

The input is a text of at most 4000 characters. It contains only characters with ASCII codes 32 (space) through 126 (~), 13 (carriage return), and 10 (line feed).

If the text has no unambiguous abbreviation with positive effectiveness, print a single line containing 0.

Otherwise print two lines. The first line contains the maximum effectiveness. The second line contains the abbreviation itself, written in uppercase letters. If several unambiguous abbreviations reach the maximum effectiveness, print the one that is lexicographically smallest when compared as uppercase strings.

An abbreviation of k words is a window of k consecutive words, and its letters are the first letters of those words. Because letters are compared case-insensitively, Jingle bells and jingle bells are the same sequence of words.

The lexicographic tie-break makes the answer unique. For a text in which the phrase not abbreviation repeats, both NA and INA can reach the maximum effectiveness, and INA is printed because it is lexicographically smaller than NA.