C. Word Expansion
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a word $$$s$$$, we want to apply a transformation $$$k$$$ times. The transformation consists of replacing all occurrences of the letter $$$a$$$ with the word $$$p_{a}$$$, all occurrences of $$$b$$$ with $$$p_{b}$$$, all occurrences of $$$c$$$ with $$$p_{c}$$$, and so on.

If we apply the transformation $$$k$$$ times, what is the letter at position $$$i$$$? ($$$i = 1$$$ represents the first letter).

Input

The input consists of several cases, each case starts with the word $$$s$$$, followed by the integers $$$k$$$ and $$$i$$$.

This is followed by 26 lines, each containing a word, which corresponds to $$$p_{a}$$$, $$$p_{b}$$$, $$$p_{c}$$$...

Output

One line for each case with the letter at position $$$i$$$ after $$$k$$$ transformations.

Scoring

11 Points $$$1 \leq |s| , |p_{\text{letter}}| \leq 10, 0 \leq k \leq 1$$$

22 Points $$$1 \leq |s| , |p_{\text{letter}}| \leq 2, 0 \leq k \leq 20$$$

67 Points $$$1 \leq |s| , |p_{\text{letter}}| \leq 10, 0 \leq k \leq 10000$$$

$$$1 \leq i \leq 10^{18}$$$, and it is never greater than the final length of the word.

Example
Input
rb 2 16
mqbh
dar
owkk
h
d
qs
dxr
mo
frx
j
bld
efsa
cbyn
c
yg
x
pk
orel
nm
apqf
kho
kmco
h
wnku
w
sqmg
ljj 1 6
vsw
d
q
bx
x
v
rrbl
ptns
fw
qf
mafa
rr
sof
b
n
vqh
fb
a
x
pqc
c
hch
vfrk
l
oz
kpqp
Output
h
f