오프 밸런스

당신은 젊은 예술가들을 위한 새 미술관을 세우려는 국제 피카소식 입체파 센터(International Center for Picassonian Cubism, ICPC)의 행정실에서 일하고 있습니다. 가장 좋은 설계를 뽑기 위해 센터는 건축 설계 공모전을 열고 있습니다.

제출된 설계는 모두 아래와 같이 잘 알려진 블록 쌓기 게임의 화면처럼 보입니다.

센터가 모든 건물을 조각(piece) 이라는 규칙적인 단위를 쌓아 짓도록 요구하기 때문인데, 각 조각은 정육면체 블록 네 개로 이루어집니다. 설계는 다음 규칙도 만족해야 합니다.

모든 조각은 정렬되어 있다. 두 조각이 맞닿을 때, 맞닿는 블록의 면은 정확히 같은 위치에 놓여야 합니다.
모든 조각은 안정적이다. 조각은 단순히 쌓기만 하므로, 무너지지 않도록 무게 중심을 신중하게 배치해야 합니다.
조각들은 트리 구조를 이룬다. 오직 한 조각만 바닥에 닿고, 나머지 조각은 각각 자신의 아랫면으로 정확히 하나의 조각에만 닿습니다. 이 트리 모양은 젊은 예술가들의 무한한 잠재력을 상징합니다.
건물은 납작하다. 공사장은 곧은 해자와 고속도로 사이의 좁은 띠 모양 땅으로, 그 폭에는 블록을 하나밖에 놓을 수 없습니다. 따라서 건물 전체가 사실상 2차원(정면도)입니다.

안정성을 완전히 확인하려면 복잡한 구조 계산이 필요해 여러 날이 걸립니다. 그래서 당신은 무게 중심만 보고 명백히 불안정한 설계를 빠르게 걸러내는 일을 맡았습니다. 빠른 판정 규칙은 다음과 같습니다.

모든 블록의 무게는 같고 무게 중심은 블록의 중앙에 있다고 가정합니다. 블록의 위치는 왼쪽 아래 모서리의 $xy$ 좌표로 나타내며, 단위 길이는 블록의 한 변 길이입니다. 즉 $(x, y)$에 놓인 블록은 $(x, y)$부터 $(x+1, y+1)$까지의 단위 정사각형을 차지합니다.

한 조각에 대해, 아랫면이 다른 조각이나 바닥에 닿는 블록만 살펴봅니다. $x_L$을 그런 블록 중 가장 왼쪽 블록의 왼쪽 $x$ 좌표, $x_R$을 가장 오른쪽 블록의 오른쪽 $x$ 좌표라고 합시다. $M$을 그 조각의 누적 무게 중심의 $x$ 좌표라고 하며, 조각 $P$의 누적 무게 중심이란 $P$ 자신과 $P$가 직접 또는 간접으로 떠받치는 모든 조각을 합친 무게 중심을 뜻합니다. 그러면 그 조각은 $x_L < M < x_R$일 때에만 안정적이고, 그렇지 않으면 불안정합니다. 조각 중 하나라도 불안정하면 설계 전체가 불안정합니다.

이 규칙은 실제로는 무너지지 않을 설계도 불안정하다고 판정할 수 있습니다. 예를 들어 아래 왼쪽 설계는 이 규칙에 따라 불안정으로 판정됩니다.

또한 이 규칙은 경계인 경우도 불안정으로 봅니다. 예를 들어 위 오른쪽 설계에서 맨 위 조각의 무게 중심은 바로 아래 조각의 오른쪽 끝 위에 정확히 놓여 있으므로 불안정으로 판정됩니다.

위의 빠른 판정 규칙으로 각 설계의 안정성을 판정하는 프로그램을 작성하세요.

입력은 여러 개의 데이터셋으로 이루어지며, 공백으로 구분된 두 개의 0만 있는 줄로 끝납니다. 각 데이터셋은 건물 하나의 정면도를 나타내며 다음 형식을 따릅니다.

w h
(y = h-1 인 줄)   맨 윗줄, 문자 w개
...
(y = 1 인 줄)
(y = 0 인 줄)     바닥에 닿는 맨 아랫줄

공백으로 구분된 정수 $w$와 $h$는 각각 배치의 열 수와 행 수이며 $1 \le w \le 10$, $1 \le h \le 60$입니다. 이어지는 $h$개의 줄은 조각의 배치를 맨 윗줄($y = h-1$)부터 맨 아랫줄($y = 0$)까지 순서대로 나타냅니다. 각 문자 $p_{xy}$는 칸 $(x, y)$의 상태로, .(빈 칸)이거나 한 자리 숫자 1–9(어떤 조각에 속한 블록)입니다.

같은 숫자를 가진 두 블록이 위, 아래, 왼쪽, 오른쪽 면 중 하나로 맞닿아 있으면 같은 조각에 속합니다. (서로 닿지 않는 한, 서로 다른 두 조각이 같은 숫자를 쓸 수도 있습니다.) $(x, 0)$에 있는 블록은 아랫면이 바닥에 닿습니다.

각 데이터셋의 조각들은 위에서 설명한 대로 올바른 트리를 이룬다고 가정해도 됩니다.

오프 밸런스

문제

입력

출력