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