육각형 타일 방정식

이 퍼즐은 육각형 타일들을 빈틈없이 이어 붙여 만든다. 각 타일에는 문자 하나가 적혀 있는데, 숫자이거나 =, 또는 사칙연산 기호 +, -, *, / 중 하나다.

모든 타일을 정확히 한 번씩 지나는 연속된 경로를 생각하자. 경로 위의 각 타일은 바로 앞 타일과 인접해 있어야 한다. 경로를 따라 문자를 읽으면 하나의 문자열이 되는데, 목표는 그 문자열이 아래에서 정의하는 올바른 등식이 되도록 경로를 고르는 것이다. 예를 들어 어떤 경로는 6/3=9-7을, 다른 경로는 3*21+10=73을 만들 수 있다.

크지 않은 배치에도 가능한 경로는 매우 많으므로, 해를 자동으로 찾는 것이 이 문제의 목표다.

짧은(홀수 번째) 행은 긴(짝수 번째) 행보다 타일 반 칸만큼 안쪽으로 들어가 있다. 따라서 두 타일이 서로 인접하다는 것은 다음 중 하나를 뜻한다. 같은 행에서 바로 옆에 나란히 있거나, 이웃한 두 행에 있으면서 가로 위치가 타일 반 칸만큼 차이 나는 경우다. 그러므로 안쪽 타일은 최대 여섯 개의 타일과 맞닿을 수 있다.

모든 퍼즐의 타일 배치와 문자는 다음 규칙을 만족한다.

1. 배치의 행 수는 2보다 큰 홀수다. 홀수 번째 행들은 모두 같은 개수의 타일을 가지며, 짝수 번째 행은 홀수 번째 행보다 타일이 하나 더 많아 왼쪽과 오른쪽으로 모두 튀어나온다.
2. 배치에는 =가 정확히 하나 있다.
3. 배치에는 *가 최대 두 개까지 있다.
4. 타일은 모두 합쳐 14개 미만이다.
5. 아래 규칙에 따라, 배치에는 올바른 해가 정확히 하나 존재한다.

경로를 따라 읽은 문자열이 올바른 등식이 되려면, 문자열에 하나뿐인 =가 포함되어야 하고, = 양쪽의 식이 모두 올바른 형태여야 하며 같은 정수 값으로 계산되어야 한다. 올바른 형태와 계산 방법은 다음 규칙을 따른다.

1. +, -, *, /는 오직 이항 연산자로만 쓰인다. +나 -가 부호(단항 연산자)로 쓰이는 문자열은 올바르지 않다. 예를 들어 -2*3=-6과 1=5+-4는 올바르지 않다.
2. 연산자 우선순위는 적용하지 않는다. 모든 연산의 우선순위가 같고, 왼쪽에서 오른쪽으로 순서대로 계산한다. 예를 들어 44-4/2=2+3*4는 올바르지만 14=2+3*4는 올바르지 않다.
3. 나눗셈은 결과가 정확히 정수로 떨어질 때만 허용된다. 예를 들어 10/5=12/6과 7+3/5=3*4/6은 올바르다. 반면 5/2*4=10은 중간에 분수가 생겨야 하므로 올바르지 않고, 5/2*4=8도 나눗셈을 버림해야 성립하므로 올바르지 않다.
4. 숫자는 최대 두 자리까지만 붙어 나올 수 있다. 예를 들어 123+1=124는 올바르지 않다.
5. 0 바로 뒤에 다른 숫자가 오는 것은 올바르지 않다. 예를 들어 3*05=15는 올바르지 않다.

이 규칙 아래에서는 중간이나 최종 계산값의 절댓값이 삼백만을 넘는 일이 결코 없다.

입력은 1개 이상 15개 이하의 데이터 집합으로 이루어지며, 마지막에는 0 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 공백으로 구분된 두 정수 r과 c가 있다. r은 배치의 행 수, c는 홀수 번째 각 행에 있는 타일의 개수다. 이어지는 r개의 줄에는 타일 문자가 한 행씩 적혀 있으며, 한 행 안의 문자들은 공백으로 구분된다. 홀수 번째 행은 육각형이 맞물리는 모습을 흉내 내기 위해 맨 앞에 공백 하나가 더 붙는다. 모든 배치는 위의 다섯 가지 배치 규칙을 만족한다.

각 데이터 집합마다 한 줄을 출력한다. 해를 이루는 경로를 따라 타일을 읽어 얻은, 유일하게 올바른 등식이다. 이 줄에는 공백이 없다.