F. Fibonacci Strings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddard likes strings. His partner likes Fibonacci numbers. Thus, $$$\mbox{The Fibonacci Strings!}$$$

The Fibonacci string sequence $$$F$$$ can be defined given $$$F_1,$$$ $$$F_2$$$ recursively as follows:

$$$$$$F_i = F_{i-1} + F_{i-2} \mbox{ for } i \gt 2$$$$$$

For example, for $$$F_1 =$$$"a", $$$F_2 =$$$ "b"; $$$F =$$$ {"a", "b", "ba", "bab", "babba", "babbabab", ..}

Given $$$F_1$$$, $$$F_2$$$, and two integers $$$x$$$, $$$k$$$; find the $$$k$$$-th character of $$$F_x$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

The first line of each test case contains 2 integers $$$n, m$$$ $$$(1 \le n, m \le 10^5)$$$

The second and third lines of each test case contain two strings of lowercase letters, $$$F_1$$$ of size $$$n$$$ and $$$F_2$$$ of size $$$m$$$.

The fourth line of each test case contains 2 integers $$$x, k$$$ $$$(1 \le x \le 1000, 1 \le k \le \mbox{min}(10^{18}, |F_x|))$$$

It is guaranteed that the sum of $$$n + m$$$ over all test cases does not exceed $$$10^5$$$

Output

For each test case, output a single character, the $$$k$$$-th character in $$$F_x$$$.

Example
Input
5
1 1
a
b
6 7
2 3
ab
xyz
1 2
4 4
nnnn
nnnn
1000 1000000000000000000
2 2
ab
cd
10 10
7 6
partner
secret
3 11
Output
a
b
n
b
n
Note

In the first test case, $$$F_6 =$$$ "babbabab", its $$$7$$$th character is "a".

In the second test case, $$$F_1 =$$$ "ab", its $$$2$$$nd character is "b".

In the third test case, all strings consist only of the character "n"