Pracsiu Dan (dnprx) Marele dramaturg BONIFACCI a uimit lumea teatrului cu noua sa capodoperă, Dada?!. Pentru că teatrul 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ă cum vedeți, în această 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 până 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):
Actul Textul
------------------
1 A
2 D
3 AD
4 DAD
5 ADDAD
6 DADADDAD
7 ADDADDADADDAD
Cerința
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 teatru.in conține pe prima linie trei numere naturale nenule N, P și L, separate între ele prin câte un spațiu, având semnificațiile de mai sus.
Date de ieșire
Fișierul de ieșire teatru.out va conține pe prima linie L caractere A sau D, reprezentând, în ordine, replicile spuse de actor la repetiție.
Restricții și precizări
- Fie
SNnumărul de replici din actul alN-lea. Se garantează căSN≤ 1018. 1 ≤ L ≤ 2.000.0001 ≤ P ≤ SN− L + 1(cu alte cuvinte, există L replici în actulNîncepând cu replica numărulP).- Pentru 7 puncte,
N ≤ 35,L = 1 - Pentru 13 puncte,
N ≤ 35,L ≤ 200.000 - Pentru 17 puncte,
N ≤ 40,L ≤ 200.000 - Pentru 19 puncte,
N ≤ 46,L ≤ 200.000 - Pentru 21 puncte,
L ≤ 200.000 - Pentru 23 puncte, nu există restricții suplimentare.
Exemplul 1:
teatru.in
7 3 9
teatru.out
DADDADADD
Explicație
Actul al șaptelea are textul complet ADDADDADADDAD. Trebuie afișate caracterele de pe pozițiile 3 - 11.
Exemplul 2:
teatru.in
12 80 8
teatru.out
ADDADADD