P2636 Codebreaker

In the early morning of December 7, 1941, a U.S. Army signalman stationed at Pearl Harbor intercepted a Japanese telegram. The formal attack would begin at 8 a.m. To reduce casualties in the Pacific theater, you have been assigned to help break the ciphertext. The intelligence department already knows the number of encryption layers and the method used in each layer. Due to the urgency, you have only 1 second to crack the Japanese ciphertext.

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.

- 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 one line: a string representing the plaintext after decrypting all $N$ layers of encryption.

$N \le 1000$. Translated by ChatGPT 5