The Euclidean Algorithm (for finding the greatest common divisor) The Challenge

Write a program or function that takes two input integers, i and j, and outputs their greatest common divisor; calculated by using the Euclidean algorithm (see below).



Input

Input may be taken as a space-delimited string representation of i and j or as two separate integers. You can assume that integers will be less than or equal to 10,000. You can also assume that the input integers will not be prime to one another.



Euclidean Breakdown

The larger number between i and j is divided by the smaller as many times as possible. Then, the remainder is added. This process is repeated with the remainder and the previous number, until the remainder becomes 0.

For example, if the input was 1599 650:

1599 = (650 * 2) + 299
 650 = (299 * 2) +  52
 299 =  (52 * 5) +  39
  52 =  (39 * 1) +  13
  39 =  (13 * 3) +   0


The final number, 13, is the greatest common divisor of the two input integers. It can be visualized like this:





Output

Your output must be the breakdown in the form above, followed by a newline and the GCD. It can be output through any medium.



Examples

Inputs

18 27
50 20
447 501
9894 2628


Outputs

27 = (18 * 1) + 9
18 =  (9 * 2) + 0
9

50 = (20 * 2) + 10
20 = (10 * 2) +  0
10

501 = (447 * 1) + 54
447 =  (54 * 8) + 15
 54 =  (15 * 3) +  9
 15 =   (9 * 1) +  6
  9 =   (6 * 1) +  3
  6 =   (3 * 2) +  0
3

9894 = (2628 *  3) + 2010
2628 = (2010 *  1) +  618
2010 =  (618 *  3) +  156
 618 =  (156 *  3) +  150
 156 =  (150 *  1) +    6
 150 =    (6 * 25) +    0
6


Note: Outputs do not have to be spaced as they are above. The spacing is only for clarity. Parentheses are required.



Bonus

If your output is spaced as above, you may add a -10% bonus to your score.
CJam, 46 43 39 bytes

q~]$3*~\{N5$"=("3$:G'*3$Gmd")+"\}h]7&gt;NG


Try it online in the CJam interpreter.

How it works

q~]    e# Read all input, evaluate it and wrap the results in an array.
$3*    e# Sort the array and repeat it thrice.
~\     e# Dump the array and swap its last two elements.
{      e# Do:
  N    e#   Push a linefeed.
  5$   e#   Copy the sixth topmost element from the stack.
  "=(" e#   Push that string.
  3$:G e#   Copy the fourth topmost element from the stack. Save it in G.
  '*   e#   Push that character.
  3$   e#   Copy the fourth topmost element from the stack.
  Gmd  e#   Push quotient and remainder of its division by G.
  ")+" e#   Push that string.
  \    e#   Swap the string with the remainder.
}h     e#   If the remainder is positive, repeat the loop.
]7&gt;    e# Wrap the stack in an array and discard its first seven elements.
NG     e# Push a linefeed and G.