Hex Tile Equations

A puzzle is built from hexagonal tiles packed tightly together. Each tile shows one character: a digit, an =, or one of the arithmetic operators +, -, *, or /.

Consider a continuous path that passes through every tile exactly once, where each tile on the path is an immediate neighbor of the previous tile. Reading the characters along the path spells out a string, and the goal is to choose a path whose string is an acceptable equation as defined below. For instance, one path through a pattern might spell 6/3=9-7, while another might spell 3*21+10=73.

Even a modestly sized pattern hides many possible paths, so your task is to find the solution automatically.

Because the shorter (odd-numbered) rows are inset by half a tile relative to the longer (even-numbered) rows, two tiles are immediate neighbors exactly when either they lie in the same row side by side, or they lie in two consecutive rows with their horizontal positions differing by half a tile. An interior tile can therefore touch up to six others.

The tile arrangement and characters in every puzzle obey these rules:

1. The pattern has an odd number of rows, greater than 2. Every odd-numbered row holds the same number of tiles, and every even-numbered row holds one more tile than the odd rows, sticking out on both the left and the right.
2. There is exactly one = in the pattern.
3. There are at most two * characters in the pattern.
4. There are fewer than 14 tiles in total.
5. Under the rules below, the pattern has exactly one acceptable solution.

For the string read along a path to be an acceptable equation, it must contain the single =, and the expressions on both sides must be in acceptable form and evaluate to the same integer. Acceptable form and evaluation are governed by these rules:

1. +, -, *, and / are binary operators only; a string in which + or - would act as a unary sign is not acceptable. For example, -2*3=-6 and 1=5+-4 are not acceptable.
2. Operator precedence is not used: every operation has equal precedence and they are applied strictly from left to right. For example, 44-4/2=2+3*4 is acceptable, but 14=2+3*4 is not.
3. A division is allowed only when it produces an exact integer. For example, 10/5=12/6 and 7+3/5=3*4/6 are acceptable, whereas 5/2*4=10 is not (it would require a fractional intermediate result) and 5/2*4=8 is not (it would require truncating division).
4. At most two digits may appear together. For example, 123+1=124 is not acceptable.
5. A 0 immediately followed by another digit is not acceptable. For example, 3*05=15 is not acceptable.

Under these rules, no intermediate or final value ever exceeds three million in magnitude.

The input contains one to fifteen datasets, followed by a line containing only 0.

The first line of each dataset holds two blank-separated integers r and c, where r is the number of rows in the pattern and c is the number of tiles in each odd-numbered row. The next r lines list the tile characters, one row per line, with the characters in a row separated by blanks. Odd-numbered rows also begin with an extra leading blank, mirroring the way the hexagons interlock. Every pattern satisfies the five arrangement rules above.

For each dataset, print a single line: the unique acceptable equation obtained by reading the tiles along the solving path. The line contains no spaces.