Problem description
Jasio, zgłębiając tajniki informatyki, przeczytał ostatnio o morfizmach na słowach i ich zastosowaniach do tworzenia zbiorów słów takich jak słowa Thuego-Morse’a lub słowa Fibonacciego.
Jasio postanowił wymyślić swój własny morfizm. Zdefiniował go
następująco: J0 = S dla
ustalonego, ulubionego słowa Jasia S składającego się jedynie ze znaków
a oraz b. Następnie Jasio zdefiniował regułę
podstawiania, która pozwala ze słowa Ji uzyskać słowo
Ji + 1:
każde wystąpienie litery a zamienia na słowo
bab, zaś każde wystąpienie litery b zamienia
na aaa.
Jeśli przykładowo S to
słowo baba, to słowo J1 jest równe
aaababaaabab. W podobny sposób ze słowa J1 można uzyskać słowo
J2: zaczynałoby się
od babbabbabaaabab.... Jaś zastanawia się nad tym jak
wygląda słowo JN. Dokładniej,
chciałby poznać wycinek JN[L…R]
czyli fragment słowa JN od L-tego do R-tego znaku. Pomożesz mu?
Wejście
W pierwszym wierszu wejścia znajduje się niepusty ciąg znaków
a i b – słowo S. W drugim (ostatnim) wierszu
wejścia znajdują się trzy liczby naturalne N, L oraz R, oddzielone pojedynczymi
odstępami.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinien się znaleźć ciąg znaków o długości R − L + 1 – fragment słowa JN od L-tego do R-tego znaku włącznie.
Znaki słowa numerujemy kolejnymi liczbami naturalnymi, zaczynając od 1.
Ograniczenia
Długość słowa S nie przekracza 100.
1 ≤ N ≤ 30, 1 ≤ L ≤ R ≤ |JN|, R − L + 1 ≤ 100 000.
Przykład
| Wejście | Wyjście | |
|
|