Untitled

Faci parte din comisia Olimpiadei Judetene de Informatica, editia 2026, clasele 11-12 si doresti sa propui o problema draguta. Din pacate, nu ai inspiratie pentru nume :(. Dupa o consultare cu ceilalti membri ai comisiei, te-ai gandit sa stabilesti numele problemei in felul urmator:

Numele problemei va fi format dintr-o permutare a primelor $K$ litere mici ale alfabetului englez, cu urmatoarele proprietati:

• valoarea absoluta a diferentei numerelor de ordin ale oricaror doua litere consecutive este mai mica sau egala cu $P$ (ex: |'a'-'b'| = 1, |'e'-'c'| = 2, |'a'-'y'| = 24);
• nu exista doua vocale vecine in nume (ex: abc este un nume valid, pe cand eabcd nu este un nume valid, fiindcă e și a (vocale) sunt alăturate)

Cerință

Cerinta $1$: Sa se determine cati candidati exista pentru numele problemei.
Cerinta $2$: Dandu-se $Q$ query-uri de forma $ord$, sa se determine cel de-al $ord$-lea candidat in ordine lexicografica.

Date de intrare

Pe prima linie se vor afla numerele naturale $cer$, $K$ si $P$, dupa cum sunt descrise in enunt.

Daca $cer = 2$:

• Pe a doua linie se va afla un numar natural $Q$, reprezentand numarul de query-uri.
• Pe a treia linie se vor afla $Q$ numere naturale, reprezentand numerele de ordine ale candidatilor ceruti.

Date de ieșire

Daca $cer = 1$:

• Pe prima linie se va afisa numarul de solutii, numar care poate fi reprezentat pe $64$ de biti cu semn.

Daca $cer = 2$:

• Pe linia $i$ se va afisa candidatul corespunzator celui de-al $i$-lea query.

Restricții și precizări

• $1 \leq cer \leq 2$;
• $1 \leq K \leq 20$;
• $1 \leq P \leq K$;
• $1 \leq Q \leq 100\ 000$
• Notăm numărul soluțiilor cu $nrsol$.
• $1 \leq ord \leq nrsol < 2^{63}$.
• Se garanteaza ca numarul de solutii poate fi reprezentat pe 64 de biti cu semn
• Candidatul $A$ este mai mic lexicografic decat candidatul $B$ daca exista $i$ a.i. $A_j = B_j, j < i, A_i < B_i$.
• Vocalele alfabetului englez sunt a, e, i, o si u.

Exemplul 1

untitled.in

1 3 1

untitled.out

2

Exemplul 2

untitled.in

2 3 1
2
1 2

untitled.out

abc
cba

Explicație

Candidatii sunt abc si cba. acb, spre exemplu, nu este valid, deoarece |'a'-'c'| = 2 > 1.

Exemplul 3

untitled.in

1 10 7

untitled.out

1010880

Exemplul 4

untitled.in

2 20 15
10
856468 685468 685416 8541685416 685416854 685416 6854185416 6854168541 685 41

untitled.out

abcdefghijmoltqnkrsp
abcdefghijltkmnporsq
abcdefghijlstrqopnmk
abcdefhotsqmjprlnkig
abcdefgiqjsrmlthokpn
abcdefghijlstrqopnmk
abcdefhksmpnqrjogtli
abcdefhksmpnilqgtojr
abcdefghijklmntrqops
abcdefghijklmnoqstpr

Exemplul 5

untitled.in

1 5 5

untitled.out

72

Exemplul 6

untitled.in

2 5 5
72
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

untitled.out

abcde
abced
abdce
abdec
abecd
abedc
acbde
acbed
acdbe
acdeb
acebd
acedb
adbce
adbec
adcbe
adceb
adebc
adecb
bacde
baced
badce
badec
bcade
bceda
bdace
bdeca
becad
becda
bedac
bedca
cabde
cabed
cadbe
cadeb
cbade
cbeda
cdabe
cdeba
cebad
cebda
cedab
cedba
dabce
dabec
dacbe
daceb
dbace
dbeca
dcabe
dceba
debac
debca
decab
decba
ebacd
ebadc
ebcad
ebcda
ebdac
ebdca
ecabd
ecadb
ecbad
ecbda
ecdab
ecdba
edabc
edacb
edbac
edbca
edcab
edcba