Playfair 2

The Playfair cipher spying mission has come back, after many months, to request a translation. You have been asked to write a program that uses a given Playfair square to encrypt a key! You may recall from Round 1 that we constructed this Playfair square. However, you do not need to have done the previous problem to do this one.

You will be given the following 5 x 5 grid of characters which was constructed using the keyword wheatstone. Your program should use this to encrypt given messages. Columns go down the grid and rows go across the grid to the right.

w h e a t
s o n b c
d f g i k
l m p q r
u v x y z

Remember: i and j are considered equivalent characters in a Playfair square.

Consider the plaintext jumble: We look at each sequential pair of letters, ju, mb, le. Then for each pair of letters, we construct a rectangle around the pair using the above grid.

For ju, the rectangle would be:

d f g i   <- remember i == j
l m p q 
u v x y 

Where i is the top right corner (since j and i are equivalent) and u is the bottom left corner. This 'sub-rectangle' is taken from the bottom left corner of the 5 x 5 key given above. Our program will always use this same grid to build sub-rectangles.

To get the encrypted text, take the opposite corners of the rectangles, with the letter in the same row as the first plaintext letter coming first. Thus ju encrypts to dy.

However, this method does not deal with letters in the same row/column or pairs of letters that are the same. Lucky, the full set of encryption steps are outlined below...

Hint: Skip steps 1, 2, 4, & 5 below for an easier starting point then build up to the final solution.

Take two letters at a time.

1. If these two letters are the same, then insert an x character between them. For example, if you had the text ssh, it should be processed as two pairs. The first would be sx and the second sh where the x has effectively been inserted between them. However, the text psst does not require an x since it splits into pairs ps and st.
2. If the message has an odd number of characters, add an x to the end to make the last pair. For example, foe becomes foex so we can process two pairs. However, the previous example ssh didn't need an x since we added one in the middle which made it even in length.
3. Find the position of the characters in the Playfair square.
4. If the letters appear in the same column of the square, replace them with the letters immediately below respectively (wrapping around to the top of the grid if needed). For example, if you had the pair ab they would encrypt to bi by moving down one. fv would become mh.
5. If the letters appear on the same row of the square, replace them with the letters immediately to the right (wrapping around to the left if needed). For example, cb would become sc.
6. If none of the conditions above are met, we must have a rectangle like in the first example using jumble above.
7. The first letter encrypts to the character on the same row which is on the other side of the rectangle. For example, j became d in the above example.
8. The second letter encrypts to the character on the same row which is on the other side of the rectangle. For example, u became y in the above example. Getting the correct order is important. Remember to always check to respective row.

Some picture examples are available HERE (from Wikipedia).

Input

The plaintext on one line. There will be no capitals, punctuation, or spaces. The plaintext will be at least 1 and at most 1000 characters. A plaintext will never contain two consecutive x characters.

Output

The encrypted ciphertext on one line.

Subtasks

Subtasks are cumulative.

• Subtask 1 (40%) The plaintext will be of even length and not require any x characters to be added, all pairs will create a rectangle. i.e. you can ignore rules 1, 2, 4 & 5.
• Subtask 2 (30%) The plaintext will be of even length and not require any x characters to be added. i.e. you can ignore rules 1 & 2.
• Subtask 3 (30%) The full solution.

If you are spending too long on this problem, move on and give the subtasks of the next problem a go for some easy points.