出题人太菜，暂无测试数据。

Topic Background

The Virginia cipher (also known as the \(Vigenère\ cipher\)) is an encryption algorithm that uses a series of Caesar ciphers to form a cipher alphabet, and belongs to a simple form of multi-table cipher.

The Virginia cipher has been invented several times. The method was first documented in the book <q>The Cipher of Mr. Giovan Battista Bellaso</q> (Italian: \(La\ cifra\ del.\ Sig.\ Giovan\ Battista\ Bellaso\)) by Giovan Battista Bellaso in 1553. However, it was later misrepresented in the 19th century as having been created by the French diplomat \(Blaise\ De\ Vigenère\), and is now known as the <q>Virginia Code</q>.

The Vigenère cipher is known for its simplicity and ease of use, as well as being difficult for beginners to decipher, and is therefore also known as the <q>unbreakable cipher</q> (French: \(le\ chiffre\ indéchiffrable\)). This has led many people to use the Virginia cipher for encryption purposes just to break it.

Title Description

The Virginia cipher is a key \(k_i(i \in [1,d])\) given by a sequence of \(d\) letters, and \(k_i\) determines the number of shifts for the \(i+t_d\) (\(t\) is an integer) letter.

Modern Virginia cipher substitution table is as follows, the first row of the key, the first column of plaintext, a plaintext corresponding to the key encryption of the resulting ciphertext that is the letter of the row at the column.

Input and output formats

Input format

First line an integer \(t\), representing the number of operations.

The next \(3n\) lines:

Line \(i\), a string \(s\) consisting of all letters;

Line \(i + 1\) a string of all lowercase letters \(k\) representing the key;

Line \(i + 2\) an integer \(op\), where \(op\) is \(0\) for encryption and \(1\) for decryption.

Output format

A total of \(n\) lines, one string per line, representing the result of the operation.

Sample

Input

2
WhichFruitULike
apple
0
WwxnlFgjtxUAxvi
apple
1

Output

WwxnlFgjtxUAxvi
WhichFruitULike

Sample Explanations

1. plaintext: \(s = \texttt{WhichFruitULike}\)

   key: \(k = \texttt{apple}\)

   First letter plaintext \(s_1 = \texttt{W}\), key \(k_1 = \texttt{a}\), encrypted against the Virginia cipher table the ciphertext is \(\texttt{W}\).

   \(\dots\)

   Sixth letter plaintext \(s_6 = \texttt{F}\), key \(k_6\) does not exist, so reset key \(k_1 = \texttt{a}\), encrypted against Virginia cipher table ciphertext is \(\texttt{F}\).

   \(\dots\)

   The fifteenth letter plaintext \(s_{15} = \texttt{e}\), the key \(k_5 = \texttt{e}\), and the ciphertext encrypted against the Virginia cipher table is \(\texttt{i}\).

   Therefore, the final encrypted ciphertext is \(\texttt{WwxnlFgjtxUAxvi}\).

2. ciphertext: \(s = \texttt{WwxnlFgjtxUAxvi}\).

   Ciphertext: \(k = \texttt{apple}\).

   First letter ciphertext \(s_1 = \texttt{W}\), key \(k_1 = \texttt{a}\), decrypted against the Virginia cipher table the plaintext is \(\texttt{W}\).

   \(\dots\)

   Sixth letter cipher \(s_6 = \texttt{F}\), key \(k_6\) does not exist, so reset key \(k_1 = \texttt{a}\), decrypted against the Virginia cipher table the plaintext is \(\texttt{F}\).

   \(\dots\)

   The fifteenth-letter ciphertext \(s_{15} = \texttt{e}\), the key \(k_5 = \texttt{e}\), and the plaintext decrypted against the Virginia cipher table is \(\texttt{i}\).

   Therefore, the final decrypted plaintext is \(\texttt{WhichFruitULike}\).

Data range

\(1 \le t \le 100\);

\(1 \le |s|, |k| \le 100\).

Tip

Virginia cipher table

If you need a Chinese translation, click here.