Крестики-нолики
Крестики-нолики — одна из древнейших игр в истории человечества. Первые упоминания об этой игре относятся к первому веку до нашей эры, временам Римской империи. Джон и Мэри любят играть в эту игру, но вскоре решили попробовать её вариант — Крестики-нолики 1-D.
Крестики-нолики 1-D — это игра для двух игроков на доске размером 1×N, где изначально все клетки пусты. Игроки по очереди ставят крестик на любую пустую клетку. Побеждает тот, кто первым составит последовательность из трёх или более крестиков в соседних клетках.
Мэри заметила, что в зависимости от текущей ситуации на доске, она может гарантировать себе победу, если ходит первой, независимо от действий Джона. Это легко сделать на небольших досках, но на больших досках, после нескольких ходов, задача усложняется. Поэтому она попросила вас создать программу, которая, анализируя текущее состояние доски, определяет, есть ли у неё выигрышная стратегия.
Входные данные
Входные данные содержат несколько тестов. Первая строка каждого теста содержит целое число N, обозначающее размер доски (3 ≤ N ≤ 10^4). Следующая строка представляет собой последовательность из N символов, показывающих состояние клеток: '.' означает, что клетка пуста, а 'X' — что на клетке уже стоит крестик. Входные данные гарантируют, что три смежных 'X' никогда не встречаются.
Последний тест заканчивается строкой, содержащей одно число ноль.
Выходные данные
Для каждого теста ваша программа должна вывести одну строку с одним символом: 'S', если у Мэри есть выигрышная стратегия, или 'N', если такой стратегии нет.