bifo

Pentru a-şi vindeca rana provocată de Spânul cel Negru, prinţul Algorel are nevoie de leacul miraculos aflat în posesia vrăjitoarei din pădurea întunecată.

Aceasta i-a promis leacul dacă îi rezolvă următoarea problemă, la care ea s-a gândit zadarnic o mie de ani: pornind de la două cuvinte iniţiale $A_1$ şi $A_2$ şi aplicând „formula bifo” $A_n = A_{n-2} \cdot A_{n-1}$ pentru $n \geq 3$, se obţin cuvintele $A_3, A_4, A_5$, ş.a.m.d. Prin $A_{n-2} \cdot A_{n-1}$ înţelegem concatenarea cuvintelor $A_{n-2}$ şi $A_{n-1}$ în această ordine. Toate aceste cuvinte ($A_1, A_2, A_3, A_4, A_5$ ş.a.m.d),sunt la rândul lor concatenate, în ordine, formând un şir de caractere infinit denumit şir magic. Formula leacului miraculos are $M$ caractere, pe care vrăjitoarea nu le ştie. Se ştiu însă cele M poziţii din şirul magic în care apar, în ordine, caracterele din formulă.

Cerință

Cu toată inteligenţa lui, Algorel nu poate rezolva această problemă. Ajutaţi-l pe prinţ să iasă din încurcătură aflând formula leacului magic.

Date de intrare

Primele două linii ale fişierului bifo.in conţin fiecare câte un şir de cel mult $100$ de caractere reprezentând cuvintele $A_1$ (pe prima linie) şi respectiv $A_2$ (pe a doua linie). A treia linie conţine un număr întreg $M$, reprezentând numărul de caractere din formula leacului miraculos. Urmează $M$ linii descriind, în ordine, poziţiile din şirul magic unde se găsesc caracterele din formulă.

Date de ieșire

Fişierul de ieşire bifo.out va conţine pe prima linie un şir de $M$ caractere reprezentând formula leacului miraculos.

Restricții și precizări

• $1 \leq M \leq 100$
• $A_1$ şi $A_2$ conţin doar litere mici ale alfabetului englez
• Numerotarea poziţiilor din şirul infinit începe cu $1$
• Cele $M$ poziţii vor fi numere întregi (nu neapărat distincte) de maxim $100$ de cifre
• Pentru $60$% din teste poziţiile vor fi numere întregi între $1$ şi $1 \ 000 \ 000 \ 000$
• Fiecare linie din fişierul de intrare şi din fişierul de ieşire se termină cu marcaj de sfârşit de linie

Exemplu

bifo.in

ab
cdx
3
10
4
15

bifo.out

xdb

Explicație

Primele $5$ şiruri de caractere obţinute folosind „formula bifo” sunt: $ab, cdx, abcdx, cdxabcdx, abcdxcdxabcdx$

Concatenând aceste şiruri se obţine şirul magic: $abcdxabcdxcdxabcdxabcdxcdxabcdx$...