Playfair Cipher

The Playfair cipher is a manual symmetric encryption technique and was the first digraph substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair, who promoted the use of the cipher.

The Playfair cipher uses a 5×5 table containing each letter of the English alphabet exactly once (except 'Q', which is omitted). This table is the encryption key. To make the table easier to remember, it is usually generated from a key phrase. First fill the empty table with the letters of the key phrase (skipping spaces and any letter that already appears), then fill the remaining cells with the rest of the alphabet in order. The key phrase is written into the top rows of the table, from left to right. For example, if the key phrase is 'playfair example', the encryption key becomes:

To encrypt a message, remove all spaces and split the message into digraphs (groups of two letters). For example, 'Hello World' becomes 'HE LL OW OR LD'. Then locate each pair in the key table and apply whichever rule below matches the letter combination:

• If the two letters are the same (or only one letter is left), insert an 'X' after the first letter. Encrypt this new pair and continue (note that this shifts all of the remaining digraphs).
• If the two letters lie in the same row of the table, replace each with the letter immediately to its right (wrapping around to the left end of the row if a letter was at the right end). With the table above, the digraph 'CH' is encrypted as 'DB'.
• If the two letters lie in the same column of the table, replace each with the letter immediately below it (wrapping around to the top of the column if a letter was at the bottom). With the table above, the digraph 'VA' is encrypted as 'AE'.
• If the two letters are in neither the same row nor the same column, replace them with the letters at the other two corners of the rectangle they define, keeping each letter on its own row. The order matters: the first letter of the encrypted pair is the one on the same row as the first letter of the plaintext pair. With the table above, the digraph 'KM' is encrypted as 'SR'.

Write a program that reads a key phrase and a plaintext, and outputs the encrypted text.

The text to encrypt will never contain two 'x's in a row, nor an 'x' as its last character, since either case could make the first rule above repeat indefinitely.

The input consists of two lines. The first line is the key phrase. The second line is the text to encrypt. Each line contains between 1 and 1000 characters, inclusive. Each character is a lowercase English letter, 'a'–'z' (except 'q'), or a space. Neither line begins or ends with a space.

Output a single line containing the encrypted text in upper case. The output must contain no spaces.