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 A1 şi A2 şi aplicând „formula bifo” An = An-2An-1 pentru n ≥ 3, se obţin cuvintele A3, A4, A5, ş.a.m.d. Prin An-2An-1 înţelegem concatenarea cuvintelor An-2 şi An-1 în această ordine. Toate aceste cuvinte (A1, A2, A3, A4, A5 ş.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 de intrare bifo.in conţin fiecare câte un şir de cel mult 100 de caractere reprezentând cuvintele A1 (pe prima linie) şi respectiv A2 (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
1 ≤ M ≤ 100; A1 şi A2 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 1000000000;
Fiecare linie din fişierul de intrare şi din fişierul de ieşire se termină cu marcaj de sfârşit de linie;
Exemple
bifo.in
bifo.out
Explicaţii
ab
cdx
3
10
4
15
xdb
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...