Most Common Prefix X19796

The prefix of length n of a word w of length at least n is the word made up from the first n letters of w in the same order. We have several candidate prefixes, with lists of words where they could appear, and want to find out the one that is most common in its corresponding list.

Input

Input is a series of cases. There is at least one case. Each case is a line containing nonempty words, separated by one or more spaces, and preceded and finished by zero or more spaces. Words are made of lowercase letters. Each line contains at least one word. In each case, the word that appears first is the candidate prefix, and the rest of the line is the corresponding list of words which may or may not have the candidate as prefix. After the series of cases comes a line containing only the word END in uppercase plus arbitrary spaces.

Output

Output must be the candidate prefix, appearing as first word in some line, that is most frequent as prefix among the words within the same line, together with its frequency there. In case of ties, the output should be the candidate prefix that appears earliest.