Informatics 1

The way in which most people were taught to multiply large integers looks like this:

    57
  x 86
 ------
   342
+ 456
 ------
  4902

If you know the multiplication tables by heart, the so called long multiplication can be solved quickly and relatively simple. However, there are other ways to multiply. One of these methods is the Russian peasant algorithm. Using this method, you do not need the multiplication tables to multiply. You just need to be able to double, halve and add numbers. The Russian peasant algorithm goes as follows:

• Write the two numbers you need to multiply in the head of two columns.
• Double every number in the first column and halve every number in the second column. if the number in the second column is uneven, halve it and drop the rest.
• Cross the entire row if the number in the second column is even.
• Keep doubling, halving and crossing lines until the number in the second column equals 1.
• Add the numbers in the first column that were not crossed. the sum equals the multiplication of the two original numbers.

Below you will find the entire multiplication table that stems from the Russian peasant algorithm when we use the numbers 57 and 86 for our multiplication. We first write 57 and 86 as the head of our columns. Because 86 is an even number, we cross the entire row. Afterwards, we double 57 (114) and we halve 86 (43). We keep on doubling, halving and crossing lines until the second column equals 1. The sum of the numbers that were not crossed in the first column equals 57*86.

   57  86
114 43
228 21
456 10
912  5
1824  2
+ 3648  1
----------
4902

It is said that this method is still used by peasants in certain areas in Russia. However, the origin of the peasant multiplication remains a matter for conjecture. It possibly goes back to an old Russian book that first described the method in a (relatively) modern age. The reference to Russia in the name of the algorithm may originate from its Russian translation in the book, while the peasant reference was probably added because it was assumed that Russia consisted mostly of peasants at that time. 

It is also possible that the method originated with Old Egyptian mathematicians, because a similar method is used in the Rhind-papyrus. The method is sometimes also called the Ethiopian (peasant) method, because of its closeness to Egypt. Ethiopia and Egypt had a lot of cultural exchanges.

Input

Two strictly positive integers, each on a separate line.

Output

The output consists of consecutive lines that are produced by multiplying the numbers in the input by means of the Russian peasant method. Every line has to contain two numbers that are separated by a space. It is unnecessary to indicate which lines should be crossed. The last line of the output is the product of the numbers in the input. It is not allowed to perform a multiplication of both numbers in the program code. You have to add the numbers that were not crossed in the first column.

Example

Input:

57
86

Output:

57 86
114 43
228 21
456 10
912 5
1824 2
3648 1
4902

De manier waarop de meeste mensen grote natuurlijke getallen hebben leren vermenigvuldigen ziet er ongeveer als volgt uit

    57
  x 86
 ------
   342
+ 456
 ------
  4902

Als je de tafels van vermenigvuldiging van buiten kent, dan is deze zogenaamde lange vermenigvuldiging snel en relatief eenvoudig te berekenen. Er bestaan echter nog tal van andere manieren om te vermenigvuldigen. Een van deze methoden staat bekend als het Russische boerenalgoritme. Om een vermenigvuldiging uit te voeren volgens deze methode heb je de tafels van vermenigvuldiging niet nodig. Je moet enkel getallen kunnen verdubbelen, halveren en optellen. Het algoritme van de Russische boeren gaat als volgt:

• Schrijf de twee getallen die moeten vermenigvuldigd worden aan het hoofd van twee kolommen.
• Verdubbel telkens het getal in de eerste kolom en halveer het getal in de tweede kolom. Als het getal in de tweede kolom oneven is, deel het dan door twee en laat de rest vallen.
• Doorstreep de volledige rij als het getal in de tweede kolom even is.
• Blijf verdubbelen, halveren en doorstrepen totdat het getal in de tweede kolom gelijk is aan 1.
• Tel de niet-doorstreepte getallen uit de eerste kolom bij elkaar op. Deze som levert het product op van de twee originele getallen.

Hieronder wordt de volledige vermenigvuldigingstabel getoond die volgt uit het Russische boerenalgoritme wanneer we het gebruiken om de getallen 57 en 86 met elkaar te vermenigvuldigen. We schrijven eerst de getallen 57 en 86 als hoofding van twee kolommen. Omdat het getal in de tweede kolom in dit geval even is, doorstrepen we de volledige kolom. Daarna verdubbelen we 57 tot 114 en halveren we 86 tot 43. We blijven verdubbelen, halveren en doorstrepen totdat het getal in de tweede kolom gelijk is aan 1. De som van de niet-doorstreepte getallen uit de eerste kolom levert het product van de vermenigvuldiging op.

    57  86
   114  43
   228  21
   456  10
   912   5
  1824   2
+ 3648   1
----------
  4902

Er wordt beweerd dat deze methode nog steeds gebruikt wordt door boeren in sommige gebieden binnen Rusland. Wat er ook van zij, het blijft gissen naar de oorsprong van de boerenvermenigvuldiging. Mogelijk gaat ze terug naar een eeuwenoud Russisch boek waarin de methode voor het eerst wordt beschreven in de (relatief) moderne tijd. De verwijzing naar Rusland in de naam van het algoritme slaat vermoedelijk op de Russische vertaling ervan in dit boek, terwijl de verwijzing naar de boeren vermoedelijk werd toegevoegd door het feit dat algemeen werd aangenomen (in ieder geval in vroegere tijden) dat het Russische grondgebied bijna uitsluitend door boeren werd bevolkt. Zij het dan zeer dunnetjes.

Het zou even goed kunnen dat de methode zijn oorsprong vind in de Oud-Egyptische wiskunde, aangezien een soortgelijke procedure gebruikt wordt in de Rhind-papyrus. De methode wordt soms ook de Ethiopische (boeren)vermenigvuldiging genoemd, omdat deze twee volkeren in elkaars nabijheid woonden en heel wat culturele uitwisseling vertoonden.

Invoer

Twee strikt positieve natuurlijke getallen, elk op een afzonderlijke regel.

Uitvoer

De uitvoer bestaat uit de opeenvolgende regels die geproduceerd worden door de twee getallen uit de invoer met elkaar te vermenigvuldigen volgens het Russiche boerenalgoritme. Elke regel moet twee getallen bevatten die van elkaar worden gescheiden door een spatie. Het is niet nodig om aan te geven welke regels moeten doorstreept worden. Als laatste regel van de uitvoer moet het product van de twee getallen uitgeschreven worden. Hierbij is het niet toegelaten om in je programmacode een vermenigvuldiging van de twee getallen uit te voeren. Je moet dus de som berekenen van de getallen uit de eerste kolom die niet doorstreept werden.

Voorbeeld

Invoer:

57
86

Uitvoer:

57 86
114 43
228 21
456 10
912 5
1824 2
3648 1
4902