Description

According to intelligence, the Japanese use $3$ kinds of encryption methods:

1. Rail Fence Cipher:

The so‑called rail fence cipher divides the plaintext into groups of $L$ characters, then concatenates the first character of each group, followed by the second character of each group, and so on, forming a seemingly irregular string. The most common case is the $2$‑rail rail fence cipher.

For example, plaintext: THERE IS A CIPHER
After removing spaces: THEREISACIPHER
Group by two: TH ER EI SA CI PH ER
Take the first character of each group: TEESCPE
Then the second character of each group: HRIAIHR
Concatenate them: TEESCPEHRIAIHR.

This yields the ciphertext we need.

There may also be more rails.

Note: If the plaintext length is not divisible by the number of rails, the leftover characters form a shorter group on their own. For example:

For THERE IS A CIPHER, the $3$‑rail grouping is: THE REI SAC IPH ER.

Take the first, second, and third characters in order (the last group only has the first two). The encrypted text is: TRSIE HEAPR EICH (remove spaces).

2. Vigenère Cipher:

The Vigenère cipher first introduced the idea of a “key,” which is of great significance in cryptography.

In cryptography, the information to be encrypted is called the plaintext, denoted by $M$; the encrypted information is called the ciphertext, denoted by $C$; and the key is a parameter, i.e., the data input to the algorithm that transforms plaintext into ciphertext or ciphertext into plaintext, denoted by $k$. In the Vigenère cipher, the key $k$ is a string of letters, $k = k_1 k_2 \cdots k_n$. When the plaintext is $M = m_1 m_2 \cdots m_n$, the resulting ciphertext is $C = c_1 c_2 \cdots c_n$, where $c_i = m_i \oplus k_i$. The operation $\oplus$ follows the table below:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C -C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D -D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E -E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F -F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G -G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H -H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I -I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J -J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K -K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M -M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N -N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O -O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P -P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q -Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R -R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S -S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T -T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U -U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V -V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W -W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X -X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y -Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Notes for operating Vigenère encryption:

When the length of plaintext $M$ is greater than the length of key $k$, repeat the key $k$ cyclically.

For example, plaintext $M = Helloworld$, key $k = abc$, ciphertext $C = Hfnlpyosnd$.

3. QWE Keyboard Code:

With the popularization of keyboards, corresponding keyboard codes also appeared.

This is a common keyboard. On the left letter area, there are three rows of letters:

QWERTYUIOP

ASDFGHJKL

ZXCVBNM

Starting from the first row and the first column, replace A with Q, B with W, …, Z with M, and so on.

For example, CODING is encrypted as EGROFU.

This is a simple encryption method today, but during World War II, when keyboards were not widespread, it was a big challenge.

Input Format

• The first line contains a positive integer $N$, the number of encryption layers applied to the intercepted ciphertext.
• The second line contains a string $S$, the ciphertext after encryption.
• The next $N$ lines (i.e., lines $3$ to $N+2$) each begin with a positive integer $K$ with $1 \le K \le 3$, indicating the encryption method used for that layer.
• The methods are listed in order: the $I$‑th given method is the actual $I$‑th encryption layer in the process, where $1 \le I \le N$.
• If $K = 1$, the rail fence cipher was used; an integer $L$ follows, the number of rails used for encryption.
• If $K = 2$, the Vigenère cipher was used; a string $T$ follows, which is the key.
• If $K = 3$, the QWE keyboard code was used.

Output Format

Output one line: a string representing the plaintext after decrypting all $N$ layers of encryption.

2
YSLTRIQXSHTQTR
1 2
3

FULLSPEEDAHEAD

Hint

$N \le 1000$.

Translated by ChatGPT 5