Da Vinci Code

The Da Vinci Code is one of the most widely read but controversial books of all time. In this book, the writer Dan Brown used a very interesting encryption technique to keep a secret message. It required a great deal of intelligence to decipher the code since there was not enough information available. Here, a similar kind of problem is given with sufficient clues to solve.

In this problem, you will be given a sequence of numbers taken from the Fibonacci sequence, and a ciphertext. Your task is to decipher the text using the decryption technique described below.

Let's follow an example. Any ciphertext will consist of two lines. The first line is the key, which contains some numbers drawn from the Fibonacci sequence. The second line is the actual ciphertext.

So, given the following ciphertext:

13 2 89 377 8 3 233 34 144 21 1
OH, LAME SAINT!

the output will be:

THE MONA LISA

For this problem, assume that the first number in the Fibonacci sequence is 1, the second one is 2, and each subsequent number is found by adding the previous two numbers of the sequence. So, the Fibonacci sequence is 1, 2, 3, 5, 8, 13, …

So, how do we get the string “THE MONA LISA” from the string “OH, LAME SAINT!”? Here, some numbers are drawn from the Fibonacci sequence; they are given in the first line. The first one is 13, which is the sixth (6^th) Fibonacci number in the Fibonacci sequence. So, the first uppercase letter in the ciphertext “O” goes to the sixth (6^th) position in the output string. The second number in the input string is 2, which is the second Fibonacci number, and thus, “H” goes to the second position in the output string; then comes 89, which is the 10^th Fibonacci number, so “L”, which is the third uppercase letter in the ciphertext, goes to the 10^th position in the output string. And this process continues until the ciphertext ends, and hence, we get the string “THE MONA LISA”. Note that only uppercase letters convey the message; other characters are simply garbage.

If a Fibonacci number is missing in the input sequence, then a blank space is put at its position in the output string. In the above example, the fourth and ninth Fibonacci numbers (5 and 55) are missing. So, a blank space is inserted in the fourth and ninth positions of the output string. But there must not be any trailing spaces.

Input Specification

The input starts with a line consisting of a single number T. T test cases follow. Each test case consists of three lines. The first line contains a single positive integer N. In the second line, there are N numbers drawn from the Fibonacci sequence. The numbers will be separated from each other by spaces. Finally, the third line contains the ciphertext to be decrypted. The value of any input Fibonacci number is less than 2³¹. The length of the ciphertext will be at most 100.

Output Specification

For each test case, output a single line containing the decrypted text. Remember that the decrypted text will contain only uppercase letters and spaces.

Sample Input

1. 2
2. 11
3. 13 2 89 377 8 3 233 34 144 21 1
4. OH, LAME SAINT!
5. 15
6. 34 21 13 144 1597 3 987 610 8 5 89 2 377 2584 1
7. O, DRACONIAN DEVIL!

download as text file

Output for Sample Input

1. THE MONA LISA
2. LEONARDO DA VINCI

download as text file