The way most people learn to multiply large numbers looks something like this:

    57
×   86
-------
   342
+ 456
-------
  4902

If you know your multiplication facts, this long multiplication is quick and relatively simple.

However, there are many other ways to multiply. One of these methods is often called the Russian peasant algorithm. You don't need multiplication facts to use the Russian peasant algorithm. You only need to double numbers, cut them in half, and add them up. Here are the rules:

• Write each number at the head of a column.

• Double the number in the first column, and halve the number in the second column. If the number in the second column is odd, divide it by two and drop the remainder.

• If the number in the second column is even, cross out that entire row.

• Keep doubling, halving, and crossing out until the number in the second column is 1.

• Add up the remaining numbers in the first column. The total is the product of your original numbers.

Let's multiply 57 by 86 as an example. Write each number at the head of a column. Because the number in the second column (86) is even, cross out that entire row. Double the number in the first column ($$57 \longrightarrow 114$$), and halve the number in the second column ($$86 \longrightarrow 43$$). Keep doubling, halving, and crossing out until the number in the second column is 1. Add up the remaining numbers in the first column to obtain the product $$57 \times 86$$.

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

It is said that the algorithm "is still used by peasants in some areas, such as Russia." However, the source of the Russian Peasant designation is unexpectedly murky. It probably goes back to a few centuries old Russian book where the method has been first described in (relatively) modern times. I may only conjecture that the algorithm has acquired the Russian part of the designation in the process of translation from Russian and the Peasant part was appended due to a widely spread conviction that (at least in older times) it was mostly the peasant population that exclusively, albeit sparsely, filled the Russian vastness.

The algorithm in fact may have Egyptian roots, as a similar procedure has been routinely used in the famous Rhind Papyrus¹. It is sometimes referred to as the Ethiopian (Peasant) Multiplication. The linkage could be explained by the proximity of the two nations and intermixing of their cultures. It is curious to note in passing that the great-grandfather of the illustrious Russian poet Alexander Serge'evich Pushkin² was a blackamoor of Ethiopian origin. However, the spurious idea that Ibrahim Petrovitch Gannibal³, a page to Peter the Great⁴, may be a historic conduit for the algorithm from North Africa to Russia clashes with the Peasant part of the designation. A pity.

Input

Two integers $$m, n \in \mathbb{N}_0$$, each on a separate line.

Output

The consecutive rows that are produced by multiplying $$m$$ and $$n$$ using the Russian peasant method. Each row must contain two numbers that are separated by a space. It is not necessary to indicate which rows should be crossed.

The last row must contain the product of $$m$$ and $$n$$. It is not allowed to directly multiply these numbers in your source 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