teatru

Mare dramaturg BONIFACCI a uimit lumea cu noua sa capodoperă, Dada?!

Pentru că teatru modern este un pic minimalist, piesa are un singur actor. Pentru că teatrul modern este un pic absurd, Actul 1 constă doar din replica A, iar Actul 2 constă doar din replica D. După ce vedeți, în fiecare piesă de teatru replica este descrisă printr-un singur caracter. Și, pentru că teatrul modern este un pic repetitiv, fiecare act $K$, începând cu al treilea inclusiv, este obținut prin concatenarea actelor $K-2$ și $K-1$, în această ordine. Piesa are $N$ acte, numerotate începând de la $1$ la $N$, toate construite după această regulă. În cadrul fiecărui act, replicile sunt numerotate începând tot de la $1$.

De exemplu, primele 7 acte sunt (vă rugăm să nu aplaudați până la final):

Cerință

La repetiție, actorul și-a propus să recite, cu intonație, $L$ replici alăturate din actul al $N$-lea, începând cu replica numărul $P$, până la replica cu numărul $P + L - 1$. Determinați secvența de caractere rostite de actor la repetiție.

Date de intrare

Fișierul de intrare conține pe prima linie trei numere naturale nenule $N$, $P$ și $L$, separate între ele prin câte un spațiu.

Date de ieșire

Fișierul de ieșire va conține, pe prima linie $L$ caractere A sau D, reprezentând în ordine, replicile spuse de actor la repetiție.

Restricții

• Fie $S_N$ numărul de replici din actul al $N$-lea. Se garantează $S_N \leq 10^{18}$.
• $1 \leq L \leq 2 \ 000 \ 000$.
• $1 \leq P \leq S_N - L + 1$ (cu alte cuvinte, există $L$ replci în actul $N$ începând cu replica numărul $P$).

Exemplul 1

teatru.in

7 3 9

teatru.out

DADDADADD

Explicații

Actul al 7-lea are textul complet ADDADDADADDAD. Trebuie afișate caracterele de pe pozițiile 3-11.

Exemplul 1

teatru.in

12 80 8

teatru.out

ADDADADD