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$	$\overset{r}{⟶}$	$25$	$\overset{r}{⟶}$	$28$	$\overset{r}{⟶}$	$14$	$\overset{r}{⟶}$	$7$
$10011$	$\overset{r}{⟶}$	$11001$	$\overset{r}{⟶}$	$11100$	$\overset{r}{⟶}$	$01110$	$\overset{r}{⟶}$	$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$	$\overset{l}{⟶}$	$203$	$\overset{l}{⟶}$	$406$	$\overset{l}{⟶}$	$301$	$\overset{l}{⟶}$	$91$
$101100101$	$\overset{l}{⟶}$	$011001011$	$\overset{l}{⟶}$	$110010110$	$\overset{l}{⟶}$	$100101101$	$\overset{l}{⟶}$	$001011011$

Input

The input exists of two lines, the first containing a number $g \in N$ , and the second a number $n \in 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: