Training Site
Sideways banner

Playfair

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

Cipher creation and cracking was much simpler before computational power was increased and techniques such as frequency analysis were developed. One example of a prominent cipher is the playfair cipher. Thought to be obsolete before now, this cipher method has been suggested for you, the expert on cryptography in New Zealand, to use on a super secret spying mission...

It begins with a keyword - wheatstone will be our example here. The first step is to construct a 5 x 5 grid of letters which will be both the encryption and decryption key. Place all the unique letters from the keyword one by one into the grid (left to right, top to bottom) without repeating any. Notice that the t and e are not repeated below.

w h e a t
s o n

This is the start of our key. After we have used up the keyword, we just insert the remaining letters from the alphabet one by one into the square until we have the 5 x 5 grid required.

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

Note: Because the alphabet contains 26 letters, (not 25) we combine i and j into one letter to maintain the 5x5 grid. Represent both i and j as simply i. That means if j appears in the key, you should pretend it is i.

This forms the basis for the encryption and decryption processes. Write a program to produce this key given a keyword. Your agents will use your amazing program in the field to encrypt and decrypt their super secret spy messages.

Input

The keyword (as one word, on one line). The keyword will be at least 1 and at most 20 characters long with no spaces.

Output

Lines 1 - 5: The 5 x 5 encryption grid, space-separated and single letters.

If you are taking a while on this problem, move onto the next one! It has an easier subtask.

  • Sample Input 1

    kensington
    

    Sample Output 1

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