Забавна ломиголовка складається з набору шестикутних плиток, з кожною з яких пов'язана цифра, або '=', або арифметична операція '+', '-', '*', чи '/'. Розглянемо неперервні шляхи, які проходять через кожну плитку рівно один раз, у яких кожна наступна плитка є безпосереднім сусідом попередньої. Задача полягає у знаходженні такого шляху, щоб послідовність символів, зображена на плитках, утворювала коректне рівняння згідно обмежень, наведених нижче. Можлива послідовність подана на рисунках зверху. На Рисунку 1 якщо йти зверху вздовж сірого шляху, то отримаємо послідовність символів "6/3=9-7". Аналогічно на Рисунку 2 якщо почати з лівої нижньої 3, то можна отримати "3*21+10=73".
Існує багато шляхів на наборі шестикутних плиток навіть невеликої кількості. Гравець може разочаруватися у розв'язанні ломиголовки і захоче побачити розв'язок. Вам потрібно автоматизувати процес знаходження розв'язку.
Розміщення шестикутних плиток та вибір символів для ломиголовки повинні задовольняти наступним правилам:
1. Шестикутна дошка містить непарну кількість рядків, більшу 2. Рядки з непарними номерами містять однакову кількість плиток. Рядки з парними номерами містять на одну плитку більше, ніж рядки з непарними номерами. І ось ці, більш довші рядки, зклеєні зверху та знизу з рядками з непарними номерами.
2. На дошці знаходиться лише одна плитка '='.
3. На дошці знаходиться не більше двох символів '*'.
4. На дошці знаходиться не більше 14 плиток.
5. З врахуванням обмежень на символи, наведених нижче, завжди існує єдиний розв'язок.
Для отримання допустимого розв'язку з символів на деякому шляху, вирази з обох сторін від знаку рівності повинні мати допустимий вид і мати одне й те ж числове значення. Наступні правила визначають допустимий вид виразів з кожної зі сторін від знаку рівності і задають порядок обчислення виразу:
6. Оператори '+', '-', '*' та '/' можуть бути лише бінарними, тобто ніяка послідовність з унарним '+' чи '-' недопустима. Наприклад, вирази "-2*3=-6" та "1 =5+-4" недопустимі.
7. Тут не працює звичний пріоритет операцій. Усі операції мають однаковий приорітет і виконуються зліва направо. Наприклад, вираз "44-4/2=2+3*4" допустимий, а "14=2+3*4" недопустимий.
8. Якщо вираз містить операцію ділення, то вона допустима лише якщо її результатом буде ціле число. Наприклад, вирази "10/5=12/6" та "7+3/5=3*4/6" допустимі. А вираз "5/2*4=10" недопустимий, так як проміжний результат не є цілочисельним. Вираз "5/2*4=8" недопустимийй, так як рівність досягається лише якщо при діленні виконується операція округлення.
9. Кожне число повинно складатись не більше, ніж з двох цифр. Наприклад, вираз "123+1 = 124" не прийнятний.
10. Символьна послідовність з '0', за яким відразу йде інша цифра, недопустима. Наприклад, вираз "3*05=15" недопустимий.
Задовольняючи описаним обмеження, жоден проміжний чи кінцевий результат обчислень виразу ніколи не перевищує по модулю трьох мільйонів.
Вхідні дані містять від одного до п'ятнадцяти тестів, за якими йде рядок з єдиного 0.
Перший рядок кожного тесту містить два відокремлених пропуском цілих числа r c, де r - число рядків шестикутної сітки, а c - кількість комірок у рядках з непарними номерами. Наступні r рядків містять символи, написані на шестикутних плитках, кожен рядок сітки задається у окремому вхідной рядку. Усі символи у рядку розділено пропусками. Рядки, які відповідають непарним рядкам сітки, починаються з пропуска. Це зроблено для кращого сприйняття того, як шестикутники розміщені між собою. Властивості 1-5 мають місце.
Для кожного теста вивести один рядок. Він повинен містити єдине допустиме рівняння згідно правил 6-10. Рядок не повинен містити пропусків.