Moving Sticks

No attempts yetTime limit1sMemory limit128 MB

Problem

Here is a simple puzzle. Move one stick in the figure below so that the equation becomes correct.

That one is easy. Here is the answer.

Write a program that solves puzzles of this kind under the rules below.

  1. A puzzle has a left operand, an operator, a right operand, an equal sign, and a result. The two operands and the result are numbers written with one or more digits, and each of them is smaller than $2^{31}$.
  2. The operator and the equal sign never change. You may move only the sticks that form the digits.
  3. You can neither remove a digit nor add a new one, so every digit position holds a digit before and after the move.
  4. Leading zeros are allowed in the input and in the output, and a leading zero in the output must be printed.
  5. Each puzzle states how many sticks to move, and you must move exactly that many. A stick is moved at most once, and the place a stick came from stays empty, so no other stick may be put there.
  6. A division has to come out exactly, with no remainder.
  7. The digits are written with seven segments, as the figure below shows.

digitsegments
0top, top left, top right, bottom left, bottom right, bottom
1top right, bottom right
2top, top right, middle, bottom left, bottom
3top, top right, middle, bottom right, bottom
4top left, top right, middle, bottom right
5top, top left, middle, bottom right, bottom
6top, top left, middle, bottom left, bottom right, bottom
7top, top right, bottom right
8all seven
9top, top left, top right, middle, bottom right

Input

The input has one or more puzzles. Each puzzle sits on one line in this format.

A ⊙ B = R (n)

A, B, and R are strings of one or more digits, and none of them is longer than nine digits. ⊙ is one of the four operators +, -, *, /. n is a natural number, the number of sticks that must be moved. One or more spaces separate A, ⊙, B, =, R, and (n).

A line that holds the word EOF, without quotes, ends the input.

Output

Print one line for each puzzle.

k.␣result

k is the puzzle number counted from 1, ␣ is one space, and result is the equation after the puzzle is solved. result carries no spaces. When a puzzle has more than one answer, print the one that comes first in lexicographic order: the smallest left operand, and among those the smallest right operand. When a puzzle has no answer, print UNSOLVABLE, without quotes, in place of result.