Хрестики-нулики
Гра "хрестики-нулики" є однією з найдавніших ігор людства. Перші згадки про неї датуються першим століттям до нашої ери, за часів Римської імперії. Джон і Марія люблять грати в цю гру, але вирішили спробувати варіант старої традиційної гри, "хрестики-нулики" 1-D.
"Хрестики-нулики" 1-D — це гра для двох гравців на дошці розміром 1×N; спочатку всі клітинки дошки порожні. Гравці по черзі ставлять хрестик у порожню клітинку. Перший гравець, який зможе створити рядок з трьох або більше хрестиків у суміжних клітинках, виграє гру.
Марія швидко зрозуміла, що в залежності від ситуації на дошці, коли настає її хід, вона може забезпечити собі перемогу, незалежно від ходів Джона. Це відносно просто для менших дощок, але для більших дощок, після кількох ходів, завдання ускладнюється. Тому вона попросила вас створити програму, яка, враховуючи поточний стан дошки, визначить, чи існує виграшна стратегія.
Вхідні дані
Вхід містить кілька тестових випадків. Перша строка кожного тестового випадку містить ціле число N, що вказує на розмір дошки (3 ≤ N ≤ 10^4). Наступна строка містить послідовність з N символів, що вказують, які клітинки дошки були позначені: '.' означає, що відповідна клітинка порожня, тоді як 'X' означає, що на клітинці вже намальовано хрестик. Вхід ніколи не містить трьох суміжних 'X'.
Останній тестовий випадок супроводжується строкою, що містить одне число нуль.
Вихідні дані
Для кожного тестового випадку у вхідних даних ваша програма повинна вивести одну строку, що містить один символ: 'S', якщо у Марії є виграшна стратегія, або 'N' в іншому випадку.