The integer $$(19)_{10}$$ (decimal representation) is represented as $$(10011)_2$$ in the binary numeral system. This allows us to define the rotation to the right of a natural number as the operation that places the last digit of the binary representation before the first one. If we thus rotate the binary number $$(10011)_2$$ to the right, we obtain the binary number $$(11001)_2 = (25)_{10}$$. A given natural number can also be rotated to the right $$n$$-fold. In this case $$n$$ successive rotations are executed on the binary representation of the number. As such, the 4-fold rotation to the right of 19 equals 7, as can be seen from the following series of rotations.

$$19$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$25$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$28$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$14$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$7$$
$$10011$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$11001$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$11100$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$01110$$	$$\stackrel{\text{r}}{\longrightarrow}$$	$$00111$$

If the binary representation of an integer has leading zeroes after a ($$n$$-fold) rotation to the right, the leading zeroes are deleted.

The inverted operation that places the first digit of the binary representation of an integer at the back, is logically called a rotation to the left of the integer. Analogous to a rotation to the right, an $$n$$-fold rotation to the left is defined as a repeated execution of a rotation to the left. Hence, the $$4$$-fold rotation to the left of the number 357 equals 91, as can be seen from the following series of rotations.

$$357$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$203$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$406$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$301$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$91$$
$$101100101$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$011001011$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$110010110$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$100101101$$	$$\stackrel{\text{l}}{\longrightarrow}$$	$$001011011$$

Input

The input exists of two lines, the first containing a number $$g \in \mathbb{N}$$, and the second a number $$n \in \mathbb{N}$$.

Output

Execute an $$n$$-fold rotation of the number $$g$$, and write out the result of all intermediate steps. Execute a rotation to the right if $$n$$ is positive, and a rotation to the left if $$n$$ is negative. The following intermediate results must be written out:

the decimal representation $$g_{10}$$ of the number $$g$$
the binary representation $$g_{2}$$ of the number $$g$$
the binary representation $$g_{2}^n$$ of the number $$g$$ after $$n$$ rotations, with leading zeroes removed
the decimal representation $$g_{10}^n$$ of the number $$g$$ after $$n$$ rotations

Tip: use the built-in Python functions bin and int to convert the decimal representation of an integer to its binary representation and vice versa.

Example

Input:

19
4

Output:

Example

Input

357
-4

Output: