Co-occurrence Search

Time Limit: 1 Second    Memory Limit: 32768 KB

A huge amount of information is being heaped on WWW. Albeit it is not well-organized, users can browse WWW as an unbounded source of up-to-date information, instead of consulting established but a little out-of-date encyclopedia. However, you can further exploit WWW by learning more about keyword search algorithms.

For example, if you want to get information on recent comparison between Windows and UNIX, you may expect to get relevant description out of a big bunch of Web texts, by extracting texts that contain both keywords "Windows" and "UNIX" close together.

Here we have a simplified version of this co-occurrence keyword search problem, where the text and keywords are replaced by a string and key characters, respectively. A character string S of length n (1 <= n <= 1,000,000) and a set K of k distinct key characters a1, ..., ak (1 <= k <= 50) are given. Find every shortest substring of S that contains all of the key characters a1, ..., ak.

Input

The input is a text file which contains only printable characters (ASCII codes 21 to 7E in hexadecimal) and newlines. No white space such as space or tab appears in the input.

The text is a sequence of the shortest string search problems described above. Each problem consists of character string Si and key character set Ki (i=1, 2, ..., p). Every Si and Ki is followed by an empty line. However, any single newline between successive lines in a string should be ignored; that is, newlines are not part of the string. For various technical reasons, every line consists of at most 72 characters. Each key character set is given in a single line. The input is terminated by consecutive empty lines; p is not given explicitly.

Output

All of p problems should be solved and their answers should be output in order. However, it is not requested to print all of the shortest substrings if more than one substring is found in a problem, since found substrings may be too much to check them all. Only the number of the substrings together with their representative is requested instead. That is, for each problem i, the number of the shortest substrings should be output followed by the first (or the leftmost) shortest substring si1, obeying the following format:

the number of the shortest substrings for the i-th problem
empty line
the first line of si1
the second line of si1
...
the last line of si1
empty line for the substring termination

where each line of the shortest substring si1 except for the last line should consist of exactly 72 characters and the last line (or the single line if the substring is shorter than or equal to 72 characters, of course) should not exceed 72 characters.

If there is no such substring for a problem, the output will be a 0 followed by an empty line; no more successive empty line should be output because there is no substring to be terminated.

Sample Input

Thefirstexampleistrivial.

mfv

AhugeamountofinformationisbeingheapedonWWW.Albeititisnot
well-organized,userscanbrowseWWWasanunboundedsourceof
up-to-dateinformation,insteadofconsultingestablishedbutalittle
out-of-dateencyclopedia.However,youcanfurtherexploitWWWby
learningmoreaboutkeywordsearchalgorithms.Forexample,ifyou
wanttogetinformationonrecentcomparisonbetweenWindowsandUNIX,
youmayexpecttogetrelevantdescriptionoutofabigbunchofWeb
texts,byextractingtextsthatcontainbothkeywords"Windows"and"UNIX"
closetogether.

bWn

3.1415926535897932384626433832795028841971693993751058209749445923078164

pi

Wagner,Bach,Beethoven,Chopin,Brahms,Hindemith,Ives,Suk,Mozart,Stravinsky

Weary

ASCIIcharacterssuchas+,*,[,#,<,},_arenotexcludedinagivenstringas
thisexampleillustratesbyitself.Youshouldnotforgetthem.Onemorefact
youshouldnoticeisthatuppercaselettersandlowercaselettersare
distinguishedinthisproblem.Don'tidentify"g"and"G",forexmaple.
However,weareafraidthatthisexamplegivesyoutoomuchhint!

![GsC_l

ETAONRISHDLFCMUGYPWBVKXJQZ

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output

1

firstexampleistriv

7

nWWW.Alb

0

1

Wagner,Bach,Beethoven,Chopin,Brahms,Hindemith,Ives,Suk,Mozart,Stravinsky

1

CIIcharacterssuchas+,*,[,#,<,},_arenotexcludedinagivenstringasthisexampl
eillustratesbyitself.Youshouldnotforgetthem.Onemorefactyoushouldnoticeis
thatuppercaselettersandlowercaselettersaredistinguishedinthisproblem.Don
'tidentify"g"and"G",forexmaple.However,weareafraidthatthisexamplegivesyo
utoomuchhint!

1

ETAONRISHDLFCMUGYPWBVKXJQZ

Submit

Source: Asia 1999, Kyoto (Japan)