Clickomania

Clickomania is a puzzle that starts from a rectangular grid of cells coloured with different colours. In each step a player selects ("clicks") a cell. If the selected cell is adjacent to at least one other cell of the same colour, all cells of that colour connected to the selected cell (including itself) are removed. The resulting "hole" is filled in by neighbouring cells according to some rule, and the goal of the game is to remove every cell in the grid.

In this problem we consider the one-dimensional version of the puzzle. The starting position is a string of colours, where each colour is written as one uppercase letter. At any moment you may select (click) a letter provided that the same letter appears immediately before or immediately after it. The maximal run of that letter containing the selected one is removed, and the string is closed up to fill the gap, becoming shorter. To solve the puzzle you must remove all letters and reach the empty string. If you reach a non-empty string in which no letter can be selected, you lose.

For example, starting from the string "ABBAABBAAB", selecting the first "B" gives "AAABBAAB". Selecting the last "A" then gives "AAABBB". Selecting an "A" and then a "B" yields the empty string. On the other hand, if you first select the third "B" you obtain "ABBAAAAB", and one can check that no matter what you select afterwards you end up with either "A" or "B", a string in which nothing can be selected. Hence the order of selections must be chosen carefully. Moreover, some puzzles cannot be solved by any sequence of selections; for example, "ABBAAAAB" is unsolvable.

The following facts about solvable puzzles are known:

• The empty string is solvable.
• If $x$ and $y$ are solvable puzzles, then $xy$, $AxA$, and $AxAyA$ are also solvable for any uppercase letter $A$.
• Every other puzzle not produced by the rules above is unsolvable.

Given a puzzle, determine whether it can be solved.

The input consists of several test cases. Each test case is given on a single line containing a string of uppercase letters. Each string has at least 1 and at most 150 characters. The input is terminated by end of file.

For each test case, print solvable on its own line if there is a sequence of selections that solves the puzzle. Otherwise, print unsolvable on its own line.