URI Online Judge | 3222

Playfair Cipher

By Jimmy Mårdell FI Finland

Timelimit: 1

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 by 5 table containing each letter in the English alphabet exactly once (except ’Q’ which is missing). The table constitutes the encryption key. To more easily remember the table, it is typically generated from a key phrase. First fill in the spaces in an empty table with the letters of the key phrase (dropping spaces and duplicate letters), then fill the remaining spaces with the rest of the letters of the alphabet in order. The key phrase is written in the top rows of the table, from left to right. For instance, if the key phrase is "playfair example", the encryption key becomes

Playfair Cipher

To encrypt a message, one would remove all spaces and then break the message into digraphs (groups of 2 letters) such that, for example, ”Hello World” becomes ”HE LL OW OR LD”. Then map them out on the key table, and apply the rule below that matches the letter combination:

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

The text to encrypt will not contain two ’x’s following each other, or an ’x’ as the last character, as this might cause the first rule above to repeat itself indefinitely.

Input

The input contains two lines. The first line contains the key phrase. The second line contains the text to encrypt. Each line will contain between 1 and 1000 characters, inclusive. Each character will be a lower case English letter, ’a’ - ’z’ (except ’q’), or a space character. Neither line will start or end with a space.

Output

The output should be a single line containing the encrypted text, in upper case. There should be no spaces in the output.

Input Samples Output Samples

playfair example

hide the gold in the tree stump

BMNDZBXDKYBEJVDMUIXMMNUVIF

the magic key

i love programming competition

YDVHCWSPKNTAHKUBIPERMHGHDVRU