Кликомания
Clickomania — это головоломка, начинающаяся с прямоугольной сетки ячеек разных цветов. На каждом шаге игрок выбирает ("кликает") ячейку. Все соединенные ячейки того же цвета, что и выбранная ячейка (включая саму себя), удаляются, если выбранная ячейка соединена хотя бы с одной другой ячейкой того же цвета. Образовавшаяся "дыра" заполняется соседними ячейками по определенному правилу, и цель игры — удалить все ячейки в сетке. В этой задаче нас интересует одномерная версия проблемы. Начальная точка головоломки — это строка цветов, где каждый цвет представлен заглавной буквой.
В любой момент можно выбрать (кликнуть) букву, при условии, что такая же буква встречается до или после выбранной. Подстрока из одинаковых букв, содержащая выбранную букву, удаляется, и строка укорачивается, чтобы убрать образовавшуюся дыру. Чтобы решить головоломку, игрок должен удалить все буквы и получить пустую строку. Если игрок получает непустую строку, в которой ни одну букву нельзя выбрать, то игрок проигрывает. Например, если начать со строки "ABBAABBAAB", выбор первой "B" дает "AAABBAAB". Далее, выбор последней "A" дает "AAABBB". Выбор "A", а затем "B" приводит к пустой строке. С другой стороны, если сначала выбрать третью "B", получится строка "ABBAAAAB". Можно убедиться, что независимо от следующих выборов, мы получаем либо строку "A", либо строку "B", в которых ни одну букву нельзя выбрать. Таким образом, нужно быть осторожным в последовательности выбранных действий, чтобы решить головоломку. Более того, существуют головоломки, которые нельзя решить независимо от выбора действий. Например, "ABBAAAAB" — это неразрешимая головоломка. Известны некоторые факты о разрешимых головоломках: Пустая строка разрешима. Если x и y — разрешимые головоломки, то таковыми являются xy, AxA и AxAyA для любой заглавной буквы A. Все остальные головоломки, не охваченные вышеуказанными правилами, неразрешимы.
Дана головоломка, ваша задача — определить, можно ли ее решить.
Входные данные
Каждый случай ввода задается одной строкой. Каждая строка содержит строку из заглавных букв. Каждая строка имеет как минимум один, но не более 150 символов. Ввод завершается концом файла.
Выходные данные
Для каждого случая ввода выведите "solvable" на отдельной строке, если существует последовательность действий, которая решает головоломку. В противном случае выведите "unsolvable" на строке.