Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Shift Cipher
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 961Accepted: 154Special 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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator