We define the operation of splitting a binary number n into two numbers a, b as follows. Let 0 i1 < i2 < ... < ik be the indices of the bits (with the least significant bit having index 0) in n that are 1. Then the indices of the bits of an that are 1 are i1 , i3 , i5 , ... and the indices of the bits of bn that are 1 are i2 , i4 , i6 , ...

For example, if n is 110110101 in binary then, again in binary, we have a = 010010001 and b = 100100100.

Input

The program reads a value of n and produces two values a and b as described above.

Your program should handle integer values of n between 1 and 2^(31) - 1 (i.e. all positive integers within the range of the int type) written in standard decimal (base 10) format.

Note:

1. Your program should not prompt the user for anything. Assume that the user will enter a single value, as described above, unprompted.
2. Your program does not need to validate the input. You are guaranteed that it will be a positive integer as described above.

Output

The output should contain the integers a and b separated by a single space. Both a and b should be written in decimal format (base 10).

Examples

Input:	Output:
6	2 4
7	5 2
13	9 4

Restrictions

Your program is not allowed to use ANY of the functions defined in the math.h header file. Specifically, it is not allowed to use the pow() functions to compute values of powers of 2.

Please use C to solve this