Description

In the 16th century, the French diplomat Blaise de Vigenère designed a polyalphabetic cipher called the Vigenère cipher. The Vigenère cipher is simple and easy to use for both encryption and decryption, yet relatively hard to crack. It was widely used by the Confederate Army during the American Civil War.

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 used as input to the algorithm that converts plaintext to ciphertext or ciphertext to plaintext, denoted by $k$. In the Vigenère cipher, the key $k$ is a string of letters, $k = k_1, k_2, \dots, k_n$. When the plaintext is $M = m_1, m_2, \dots, m_n$, the ciphertext obtained is $C = c_1, c_2, \dots, c_n$, where $c_i = m_i \operatorname{\circledR} k_i$. The rules for the operation $\circledR$ are shown in the table below:

Notes when applying Vigenère encryption:

1. The $\circledR$ operation ignores the case of the letters involved, and preserves the letter case as it appears in the plaintext $M$.
2. When the length of the plaintext $M$ is greater than the length of the key $k$, repeat the key $k$.

Task: Given a plaintext and a key, perform two rounds of encryption:

• First-stage encryption: sequentially apply $n$ instructions of the form $(l, r)$, reversing the characters from the $l$-th to the $r$-th positions of the plaintext.
• Second-stage encryption: according to the above rules, apply the Vigenère cipher once more to the result of the first stage to obtain the final level-2 ciphertext.

For example, with plaintext $M=\texttt{Helloworld}$, key $k=\texttt{abc}$, $n=1$, and instruction $(4, 9)$, the level-1 ciphertext is $C_1=\texttt{Hellrowold}$, and the level-2 ciphertext is $C_2=\texttt{Hfnlsqwpnd}$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline \textsf{Plaintext} & \tt H & \tt e & \tt l & \tt l & \tt o & \tt w & \tt o & \tt r & \tt l & \tt d \\ \hline \textsf{Level-1 Ciphertext} & \tt H & \tt e & \tt l & \tt l & \tt r & \tt o & \tt w & \tt o & \tt l & \tt d \\ \hline \textsf{Key} & \tt a & \tt b & \tt c & \tt a & \tt b & \tt c & \tt a & \tt b & \tt c & \tt a \\ \hline \textsf{Level-2 Ciphertext} & \tt H & \tt f & \tt n & \tt l & \tt s & \tt q & \tt w & \tt p & \tt n & \tt d \\ \hline \end{array}$$

Input Format

The first line contains a string representing the key $k$, with length not exceeding 1000, containing only uppercase and lowercase letters.
The second line contains a string representing the plaintext before encryption, with length not exceeding 1000, containing only uppercase and lowercase letters.
The third line contains a non-negative integer $n$ ($0 \le n \le 10^5$), representing the number of instructions in the first-stage encryption.
Each of the following $n$ lines contains two positive integers $l, r$ ($1 \le l \le r \le m$), representing one instruction, where $m$ is the length of the plaintext.

Output Format

Output a single string, which is the level-2 ciphertext corresponding to the given key and plaintext.

CompleteVictory
Wherethereisawillthereisaway
0

Yvqgpxaimmklongnzfwpvxmniytm

Hint

Translated by ChatGPT 5