Description
Last Pokemon Contest (神奇寶貝華麗大賽) between Satoshi (小智) and Haruka (小遙) ! After Satoshi won the victory in Battle Pyramid, Satoshi and Haruka signed up for an unofficial Pokemon Contest in Terracotta Town.
Pokemon Contest is a contest in which trainers and Pokemons coordinate strength and beauty. It is divided into two stages. In the first stage, the Performance Stage, trainers and their Pokemons will perform moves to showcase their styles and skills. In the second stage, the Battle Stage, trainers battles against each other as well as demonstrating charm of their Pokemons.
Satoshi and Haruka met in the Battle stage, where Satoshi's Sceptile (蜥蜴王) fought against Haruka's Blaziken (火焰雞). In the final ten seconds of the battle, Satoshi's Sceptile activates Overgrow (茂盛) and fires Solarbeam (陽光烈焰). To battle in a dazzling style, the pattern of Solarbeam is cleverly designed using golden ratio, but in reversed order:
The pattern of Solarbeam can be expressed with a string. First, Satoshi and Sceptile design two short patterns F0 and F1. Then they generate longer patterns using the following recurrence formula: Fn = reverse( Fn-1 + Fn-2 ) (+ means string concatenation). Finally, Satoshi tells Sceptile a number n, and Sceptile fires the Solarbeam with pattern Fn.
Given F0, F1, n, and k, please find out the k-th character in Fn.
For full episode, please google "AG191 Satoshi vs. Haruka! Last Battle!!" or refer to this page.
Explanation on Sample IO
All test data provide same F0 = "abc", F1 = "def". We can generate the following patterns:
-
F2 = "cbafed"
-
F3 = "feddefabc"
-
F4 = "defabccbafeddef"
The first test data asks 0-th character of F0, therefore output 'a'. Similarly, the outputs for the second to fifth test data are 'd', 'd', 'c', 'b', respectively.
Input
The input contains multiple test data. The first line of input contains an integer T, being number of test data. After that are T test data.
The first line of test data contains two non-empty strings F0 and F1.
The second line of test data contains two integers n and k.
-
1 <= T <= 100
-
F0 and F1 contain only lower case alphabets (
a-z) and have length no greater than 100. -
Tiny test cases:
-
0 <= n < 10 and 0 <= k < |Fn|
-
-
Nomral test cases:
-
0 <= n < 50 and 0 <= k < |Fn|
-
-
Large test cases:
-
0 <= n < 1018 and 0 <= k < 1015
-
Output
For each test data, output the answer in a single line. Remember to add new line in the end.