Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals
Language:
Shift Cipher
 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 978 Accepted: 156 Special Judge

Description

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.

Input

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.

Output

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”.

Sample Input

we
will
meet
at
midnight

zhzloophhwdwplgqljkw
lowder
0

Sample Output

k=3: we will meet at midnight
NO SOLUTIONS

Source

[Submit]   [Go Back]   [Status]   [Discuss]