# 2698. 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 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

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.

### 输入格式

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.

### 输出格式

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

should be no spaces in the output.

### 样例

Input
playfair example
hide the gold in the tree stump
the magic key
i love programming competition

Output
BMNDZBXDKYBEJVDMUIXMMNUVIF
YDVHCWSPKNTAHKUBIPERMHGHDVRU


14 人解决，33 人已尝试。

18 份提交通过，共有 58 份提交。

6.4 EMB 奖励。