Elfii au descoperit ruinele unui vechi templu. Pe un perete se află o inscripție foarte interesantă, formată din simboluri ale lunii și ale soarelui.
    Inscripția apare sub forma unei matrice pătratice cu n linii și n coloane.
    Din nefericire, trecerea timpului a dus la deteriorarea peretelui și acum numai ultima coloană mai este vizibilă. Până la urmă, elfii au reușit să descopere o regulă interesantă chiar dacă simbolurile nu mai sunt integral vizibile.
    Se consideră simbolurile lunii și ale soarelui de pe o linie care sunt dispuse într-o ordine aparent aleatoare. Totuși, în continuare se observă o regulă foarte clară. O altă linie a matricei se obține din prima, efectuând o permutare circulară la stânga cu o poziție, adică primul element ajunge pe ultima coloană, toate celelalte sunt mutate la stânga cu o poziție. O altă linie se obține permutând din nou cu o poziție și așa mai departe, până la obținerea tuturor rândurilor.
    De exemplu, în situația ipotetică în care un rând ar fi LSLLS atunci cele cinci rânduri ale inscripției sunt:
LSLLS
SLLSL
LLSLS
LSLSL
SLSLL
    Am notat prin L simbolurile lunii și prin S cele ale soarelui.
    Este evident că toate aceste rânduri apar pe inscripție, dar ele nu se află în această ordine.
    S-a observat că există o regulă de ordonare a acestora. Singura regulă care stă la baza acestei ordonări este aceea că soarele se află, din punct de vedere al acestei ordini, înaintea lunii.
    Așadar, fiecare rând poate fi privit ca un cuvânt și aceste cuvinte sunt ordonate folosind această regulă. În acest caz, pentru linia considerată, configurația inscripției ar fi:
SLSLL
SLLSL
LSLSL
LSLLS
LLSLS
    Folosind regulile prezentate trebuie determinată prima linie a inscripției (celelalte sunt ușor de aflat dacă este cunoscută aceasta), având în vedere faptul că sunt vizibile doar simbolurile de pe ultima coloană.


Fișierul de intrare INPUT.TXT conține o singură linie pe care se află caracterele care reprezintă elementele de pe ultima coloană a inscripției.

Fișierul de ieșire OUTPUT.TXT trebuie să conțină o singură linie pe care se vor afla caracterele care reprezintă elementele de pe prima linie a inscripției.

  • numărul de linii și de coloane ale inscripției este cuprins între 1 și 50000;
  • va exista întotdeauna posibilitatea determinării soluției.


  • INPUT.TXT
    LLLSS

    OUTPUT.TXT
    SLSLL