5. Zašifrovávať budeme

Ahojte moji bratia ktorým sa otvorili oči, ako už všetci isto vieme, mimozemšťania sa snažia získať našu planétu. Našťastie, naša verná kamrátka M.i.š.k.a - Mimoriadne Iniciatívna Šifrovateľská Kamrátka (Asi) - našla spôsob, ako sa brániť. Vymyslela, ako zašifrovať všetky naše dôležité informácie, veľmi zložitým a komplexným spôsobom, že ich mimozemšťania nikdy nerozlúštia. Ako to spravila? Funguje to tak, že ku každému písmenku vymyslela náhodné slovo a následne každé písmenko z našej správy zamenila za toto slovo. Ale potom si povedala, že toto by tí ufóni mohli veľmi ľahko dekódovať. Preto to spravila znovu. Každé písmenko z novej správy vymenila za slovo jemu prislúchajúce, rovnako ako prvý krát. Stále sa jej ale správa nezdala dosť zakódovaná, tak pre istotu tento proces zopakovala ešte \(N\)-krát. Teraz je už správa veľmi dobre zakódovaná, ale keď ju posielala našim spojencom, mimozemšťania nám ukradli jedno písmenko z tejto zakódovanej správy. Pomôžte nám zistiť, ktoré písmenko nám ukradli.

Úloha

Na vstupe dostanete ku každému písmenku z abecedy priradený string nejakej náhodnej dĺžky. Taktiež tam dostanete aj pôvodnú správu a počet \(N\) (koľko krát naši vedci vymenili každé písmenko zo správy za jemu prislúchajúci string). Na záver ešte dostanete aj číslo \(K\). Vašou úlohou je vypísať \(K\)-te písmenko z výslednej správy. Ak výsledná správa je kratšia ako \(K\) tak vypíšte “Neexistuje”. Zároveň existuje aj číslo \(D\), ktoré udáva maximálnu dĺžku stringu priradeného písmenku z abecedy.

Formát vstupu

V prvom riadku vstupu je string, ktorý vedci chcú zakódovať. V tejto úlohe používame iba malé písmenká anglickej abecedy. String bude mať dĺžku aspoň \(1\) a najviac \(10^6\). V druhom riadku sú čísla \(N\) udávajúce koľko krát sa má každé písmenko zmeniť za jemu prislúchajúci string a \(K\) udávajúce koľkaté písmenko z výsledného reťazca chceme vedieť. Následuje \(26\) riadkov kde na \(i\)-tom riadku je string priradený písmenku \(i\)-temu z abecedy (na prvom riadku ku \(a\)-čku na druhom \(b\)-čku atď). V každom riadku sa nachádza alespoň 1 znak. Jediný prípad, kedy v riadku nedostanete pismenko malej abecedy je, keď sa tam bude nachádzať #. Tento znak znamená, že za písmenko vymieňame vždy prázdny string.

V jednotlivých sadách platia nasledujúce obmedzenia (kde \(D\) reprezentuje aký najdlhší môže byť string ktorým nahrádzame jednotlivé písmenká):

Zároveň ešte pre jednotlivé sady platí že:

Formát výstupu

Vypíšte buď \(K\)-te písmeno z výslednej správy (číslujúc od \(1\)) alebo “Neexistuje” ak je výsledná správa kratšia ako \(K\).

Príklady

Input:

ab
1 4
abb
cde
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#

Output:

c

z a-čka sme spravili “abb” a z b-čka “cde”, čo znamená, že z výsledného stringu “abbcde” chceme 4. písmenko, čo je c

Input:

abc
3 14
a
cdc
dd
eee
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#

Output:

Neexistuje

z našeho slova abc sa po prvej zámene stalo “acdcdd”, po druhej sa z neho stalo “addeeeddeeeeee” a po tretej “aeeeeeeeeeeee”, keďže e-čka menime na prázdny string. A keďže sa pýtame na pozíciu, ktorá vo výslednom stringu neexistuje, tak vypíšeme “Neexistuje”

Input:

zwx
4 66
qoyh
bfd
m
dsha
gnif
fyz
#
t
oeea
#
y
f
j
gr
ugf
jal
fei
#
jt
atvw
cj
jp
kpw
b
ax
ma

Output:

a

vývoj stringu: zwx -> makpwb -> jqoyhyjalkpwbfd -> feiugfaxtaxqoyhfyjalkpwbfdfyzdsha -> fyzgnifoeeacjfyzqoyhbatvwqoyhbfeiugfaxtfyzaxqoyhfyjalkpwbfdfyzdshafyzaxmadshajttqoyh