Introduction

To convert a number n into base b one must find the unique sequence of digits d₀, d₁, d₂, ... such that n = d₀ * b⁰ + d₁ * b¹ + d₂ * b²... and each d_i is between 0 and b-1 inclusive. Note that in some bases we run out of symbols to use for digits. For example, we need sixteen different digits for hexadecimal (base 16), so we use letters A through F in addition to 0 through 9.

When b=2 we have the binary number system where the legal digits are 0 and 1. 3215₁₀ = 110010001111₂ since 3215 = 1 * 2¹¹ + 1 * 2¹⁰ + 0 * 2⁹ + 0 * 2⁸ + 1 * 2⁷ + 0 * 2⁶ + 0 * 2⁵ + 0 * 2⁴ + 1 * 2³ + 1 * 2² + 1 * 2¹ + 1 * 2⁰.

Unique representation also works for any base b that is a negative odd integer less than -1. Here the valid digits are (b + 1) / 2 through (-b - 1) / 2. In other words, given an integer n one can find the unique sequence of integers d₀, d₁, d₂, ... such that n = d₀ * b⁰ + d₁ * b¹ + d₂ * b²... and each d_i has an absolute value less than (-b-1)/2 (so we are using negative numbers for digits much like how we use letters for digits in hexadecimal).

So for b = -5 the digits must be between -2 and 2 inclusive. We let d₅ = -1, d₄ = 0, d₃ = -1, d₂ = -1, d₁ = 2, d₀ = 0 and write 3215₁₀ as (-1 0 -1 -1 2 0)_-5 since 3215 = -1 * (-5)⁵ + 0 * (-5)⁴ + -1 * (-5)³ + -1 * (-5)² + 2 * (-5)¹ + 0 * (-5)⁰.

The representation of a number in a negative base can be found by the following steps:

• Find the representation of the number in the positive base by repeatedly taking the remainder when the number is divided by the base and then dividing by the base. This remainders give the digits from the 1's place up.
• Negate all the digits in the odd numbered places.
• Adjust those digits that are too small or too big.

For example, to find the base -5 representaion of 3215, we first find its representation in base 5 (using digits 0 through 4), then negate the digits in the 5's, 125's, and 3125's places, and finally adjust the digits so they are all in the valid -2 to 2 range:

• 3215 % 5 = 0, so the least significant digit is 0. 3215 / 5 = 643. 643 % 5 = 3, so the next-to-last digit (the one in the 5's place) is 3. 643 / 5 = 128. 128 % 5 = 3, so the next digit is 3. 128 / 5 = 25. 25 % 5 = 0. 25 / 5 = 5. 5 % 5 = 0. 5 / 5 = 1. 1 % 5 = 1. 1 / 5 = 0, so we stop. The base 5 representation of 3215 is then 1 0 0 3 3 0.
• Next, we negate the digits in the odd numbered places (counting the 1's place as place 0) to get -1 0 0 3 -3 0.
• Next we adjust the digits that are too big or too small, working from the 1's place towards the left.
  • The 0 in the 1's place is within the required range, so we leave it alone.
  • The -3 is too small, so add 5 (determined by the base) to get 2; however adding 5 to that place adds 5 * -5 (the place value of that digit) = -25 to the value of the number and we must adjust for that by adding 1 to the digit in the 25's place (thus adding 25 back in), yielding -1 0 0 4 2 0.
  • The 4 is too big, so we subtract 5 to get -1 and subtract 1 from the next place so the value of the number does not change.
  • The -1, 0, and -1 are all in the required range, so the result is -1 0 -1 -1 2 0.
  Note that the rule when changing digits is that if you subtract from one digit to get it in the required range, you subtract 1 from the next most significant digit; if you add to a digit to get it in the required range you add one to the next most significant digit.

Input

Output

Example

Input:

-5
1562

Output:

2 -2 2 -2 2