Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Żółwie (zol)

Żółwie

Limit pamięci: 64 MB

Jacek i Placek natknęli się na stadko zmarzniętych żółwi. Żółwie ustawione są w rzędzie, od lewej do prawej, przy czym niektóre stoją na nogach, a niektóre leżą na skorupie. Jest zbyt zimno, żeby żółwie mogły same się poruszać - nawet te, które stoją na nogach, nie uciekają.

Widząc to, chłopcy wpadli na pomysł, żeby zagrać w grę. Zacznie Jacek, a potem będą wykonywali ruchy na zmianę. W każdym ruchu należy odwrócić pewną liczbę żółwi (co najmniej jednego) na drugą stronę, przy czym są pewne ograniczenia:

Pierwszy (najbardziej z lewej) odwracany żółw musi stać na nogach, i jest odwracany na skorupę.
Odwracane żółwie muszą stać w równych odstępach.

Wygrywa ten, po czyim ruchu wszystkie żółwie leżą na skorupach.

Pomóż Jackowi stwierdzić, czy może wygrać tę grę, a jeśli tak, jaki ruch powinien wykonać.

Wejście

Jedyny wiersz wejścia zawiera ciąg liter opisujących początkowy stan żółwi, od lewej do prawej. Litera N oznacza, że żółw stoi na nogach, a S, że leży na skorupie.

Nie wszystkie żółwie leżą początkowo na skorupie.

Liczba liter będzie nie mniejsza niż i nie większa niż . W testach wartych punktów liczba liter nie przekroczy .

Wyjście

Jeśli grę może wygrać Jacek, należy wypisać stan żółwi po jednym z wygrywających ruchów Jacka, w takim samym formacie jak na wejściu. Jeśli Jacek nie może wygrać, należy wypisać jedno słowo NIE.

Przykład

Dla danych wejściowych:

NSNNN

poprawnym wynikiem jest:

NSNNS

a dla danych wejściowych:

NSNNS

poprawnym wynikiem jest:

NIE

Autor zadania: Tomasz Czajka. Zadanie zainspirowane folklorem.