Square Cipher

In Dorothy Sayers' novel "Have His Carcass", Lord Peter Wimsey describes a cipher that is easy to encode and decode by hand but fairly hard to break. Your job is to implement it.

Here is how it works, in Wimsey's slightly edited words.

You choose a key word of six letters or more, none of which recurs. Such as, for example, SQUANDER. Then you make a diagram of five squares each way and write the key word into the squares row by row, starting at the top left.

+----+----+----+----+----+
| S  | Q  | U  | A  | N  |
+----+----+----+----+----+
| D  | E  | R  |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+

Then you fill the remaining spaces with the rest of the alphabet in order, leaving out the ones you already have.

You cannot put twenty-six letters in twenty-five spaces, so you pretend you are an ancient Roman or a medieval monk and treat I and J as one letter. So you get this.

+----+----+----+----+----+
| S  | Q  | U  | A  | N  |
+----+----+----+----+----+
| D  | E  | R  | B  | C  |
+----+----+----+----+----+
| F  | G  | H  | IJ | K  |
+----+----+----+----+----+
| L  | M  | O  | P  | T  |
+----+----+----+----+----+
| V  | W  | X  | Y  | Z  |
+----+----+----+----+----+

Now take a message. What shall we say? "All is known, fly at once", that classic hardy perennial. Write it down all of a piece with the spaces dropped. It will not do to have two of the same letters standing next to each other, so wherever that happens you shove a Q in between them, which will not confuse the reader. Then break the run into groups of two letters, reading from left to right. Now the message runs:

AL QL IS KN OW NF LY AT ON CE

If there is an odd letter at the end, you add another Q to square it up.

Now take the first group, AL. The two letters come at the corners of a rectangle whose other corners are S and P, so you put down SP for the first two letters of the coded message. In the same way QL becomes SM and IS becomes FA.

Ah, but here is KN. They both come on the same vertical line. In that case you take the letter next below each, which gives TC, and when there is no letter below you start again at the top of the line. Next comes OW, which translates to MX. Going on: SK, PV, NP, TU. If your first diagonal went from bottom to top, you must take it the same way again, so ON is TU while NO would be UT. CE come on the same horizontal line. In that case you take the letter to the right of each, and since there is no letter to the right of C you start again at the beginning of the line, producing DR. Your coded message stands now:

SP SM FA TC MX SK PV NP TU DR

In the novel, to make it look pretty and not give the method away, you break the ciphertext into any lengths you like and embellish it with haphazard punctuation.

S.P. SMFA. TCMXS, KPVM, PT! UDR.

Your program does not do that. It prints plain two-letter groups.

It is very ingenious. You cannot guess it by way of the most frequent letter, because a letter comes out differently each time according as it is grouped with the next one, and you cannot guess individual words, because you do not know where the words begin and end. Is it at all possible to decode it without the key word?

"Oh dear, yes," said Wimsey. "Any code ever coded can be decoded with pains and patience."

The input is a series of key words and messages to encode, alternating line by line, until a line that holds 999 alone. Encode each message with the key word on the line right above it.

Every line is upper case and holds no punctuation. A message may be split into words by single spaces, and those spaces are not part of the message. Unlike the example above, a key word may repeat a letter, in which case you ignore every occurrence after the first. A J counts as an I, both in a key word and in a message.

For each message print one line: the encrypted text written as two-letter groups separated by a single space, with no punctuation. Print an I for the cell that holds I and J.

If the odd letter left at the end is also a repeat, treat it as a repeat and put the Q before it, not afterward. That is, ALL becomes ALQL for encoding purposes.

In the unlikely case of two Qs in a row, insert a Z between them. Also, square up an odd-length message ending with a Q by using a Z. Thus FAQQAD becomes FAQZQADQ and HUQ becomes HUQZ for encoding.