3395：Shift Cipher

A cryptosystem is a method to convert a message into a cipher, which is difficult to understand by unauthorized people. Assume that both the message and the cipher are strings over the alphabet {a, b, …, z}.

A shift cipher is a cryptosystem that shifts each character in the message by k positions. For example, if k = 3, then a is converted into d, b into e, …, x into a, y into b, and z into c. The number k is called the key of the cryptosystem.

To make the cipher more difficult to understand, spaces and all punctuations are removed from the message before encryption. For example, assume that k = 3, the message:

we will meet at midnight.

is encrypted into the cipher:

zhzloophhwdwplgqljkw

For simplicity, we assume that a message is recovered if spaces are inserted into the text so that each word separated by spaces is a word in the dictionary. Given a cipher text write a program to recover the message. You may assume that each cipher is less than 256 characters, and each word used in the message appears in the dictionary. The dictionary is located at the very beginning of the input, succeeded by a single blank line. This dictionary is plain text; each line contains a word. There are words with capital or special letters in the dictionary. These words will not be used in our system. It is not necessary to check if the sentence is grammatically correct or not. The answer will be considered correct if no adjacent words are single character and the average number of characters in the words is greater than 2.

The input data is a set of ciphers. Each cipher is written in a line. A line containing only the character 0 signals the end of a test data.

The output is the key k and the recovered message for each of the cipher. Print the solution of each test case in a line. If the solution is not unique, print the solution with minimum number of words. If there is no solution, print “NO SOLUTIONS”.