클리코매니아

클리코매니아(Clickomania)는 서로 다른 색으로 칠해진 셀들로 이루어진 직사각형 격자에서 시작하는 퍼즐이다. 각 단계에서 플레이어는 셀 하나를 선택("클릭")한다. 선택한 셀이 같은 색의 다른 셀과 하나라도 인접해 있다면, 선택한 셀과 연결된 같은 색 셀 전체(자기 자신 포함)가 제거된다. 이렇게 생긴 "구멍"은 어떤 규칙에 따라 주변 셀로 채워지며, 격자의 모든 셀을 제거하는 것이 게임의 목표이다.

이 문제에서는 이 퍼즐의 1차원 버전을 다룬다. 시작 상태는 색을 나타내는 문자열이고, 각 색은 하나의 대문자로 표현된다. 임의의 시점에서, 선택한 문자와 같은 문자가 그 바로 앞이나 바로 뒤에 있는 경우에만 그 문자를 선택(클릭)할 수 있다. 선택한 문자를 포함하며 같은 문자가 연속으로 이어진 구간이 통째로 제거되고, 빈 자리는 메워져 문자열이 짧아진다. 퍼즐을 풀려면 모든 문자를 제거해 빈 문자열을 만들어야 한다. 문자열이 비어 있지 않은데 어떤 문자도 선택할 수 없는 상태가 되면 플레이어는 패배한다.

예를 들어 문자열 "ABBAABBAAB"에서 시작한다고 하자. 첫 번째 "B"를 선택하면 "AAABBAAB"가 된다. 이어서 마지막 "A"를 선택하면 "AAABBB"가 된다. 다시 "A"를 선택하고 이어서 "B"를 선택하면 빈 문자열이 된다. 반면 처음에 세 번째 "B"를 선택하면 "ABBAAAAB"가 되는데, 이후 어떤 선택을 하더라도 결국 "A" 또는 "B"만 남아 더 이상 아무 문자도 선택할 수 없게 됨을 확인할 수 있다. 따라서 퍼즐을 풀려면 선택 순서를 신중히 골라야 한다. 나아가, 어떤 순서로 선택하더라도 풀 수 없는 퍼즐도 존재한다. 예를 들어 "ABBAAAAB"는 풀 수 없는 퍼즐이다.

풀 수 있는 퍼즐에 대해서는 다음 사실이 알려져 있다.

• 빈 문자열은 풀 수 있다.
• $x$와 $y$가 풀 수 있는 퍼즐이면, 임의의 대문자 $A$에 대해 $xy$, $AxA$, $AxAyA$도 풀 수 있다.
• 위 규칙으로 만들어지지 않는 그 밖의 모든 퍼즐은 풀 수 없다.

주어진 퍼즐이 풀 수 있는지 판정하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄로 주어지며, 대문자로 이루어진 문자열 하나를 담고 있다. 각 문자열의 길이는 1 이상 150 이하이다. 입력은 파일의 끝(EOF)에서 종료된다.

각 테스트 케이스마다, 퍼즐을 풀 수 있는 선택 순서가 존재하면 한 줄에 solvable을 출력한다. 그렇지 않으면 한 줄에 unsolvable을 출력한다.