Клікоманія
Clickomania — це головоломка, яка починається з прямокутної сітки клітин різних кольорів. На кожному кроці гравець вибирає ("натискає") клітину. Усі з'єднані клітини того ж кольору, що й вибрана клітина (включаючи саму себе), видаляються, якщо вибрана клітина з'єднана хоча б з однією іншою клітиною того ж кольору. Утворена "дірка" заповнюється сусідніми клітинами за певним правилом, і метою гри є видалити всі клітини в сітці. У цій задачі нас цікавить одномірна версія задачі. Початкова точка головоломки — це рядок кольорів (кожен представлений великою літерою).
У будь-який момент можна вибрати (натиснути) літеру за умови, що така ж літера зустрічається перед або після вибраної. Підрядок з однакових літер, що містить вибрану літеру, видаляється, і рядок скорочується, щоб видалити утворену дірку. Щоб розв'язати головоломку, гравець повинен видалити всі літери і отримати порожній рядок. Якщо гравець отримує непорожній рядок, у якому жодну літеру не можна вибрати, то гравець програє. Наприклад, якщо почати з рядка "ABBAABBAAB", вибір першої "B" дає "AAABBAAB". Далі, вибір останньої "A" дає "AAABBB". Вибір "A", а потім "B" дає порожній рядок. З іншого боку, якщо спочатку вибрати третю "B", отримуємо рядок "ABBAAAAB". Можна перевірити, що незалежно від наступних виборів, ми отримуємо або рядок "A", або рядок "B", у якому жодну літеру не можна вибрати. Таким чином, потрібно бути обережним у виборі послідовності виборів, щоб розв'язати головоломку. Крім того, існують головоломки, які не можна розв'язати незалежно від вибору. Наприклад, "ABBAAAAB" — це нерозв'язна головоломка. Відомі деякі факти про розв'язні головоломки: Порожній рядок є розв'язним. Якщо x і y — розв'язні головоломки, то такими ж є xy, AxA і AxAyA для будь-якої великої літери A. Усі інші головоломки, не охоплені наведеними правилами, є нерозв'язними.
Дано головоломку, ваше завдання — визначити, чи можна її розв'язати.
Вхідні дані
Кожен випадок вхідних даних задається одним рядком. Кожен рядок містить рядок з великих літер. Кожен рядок має принаймні одну, але не більше ніж 150 символів. Введення завершується кінцем файлу.
Вихідні дані
Для кожного випадку вхідних даних виведіть розв'язна на одному рядку, якщо існує послідовність виборів, яка розв'язує головоломку. В іншому випадку виведіть нерозв'язна на рядку.