Algorithms and Data Structures

# Negative numbers in binary

So far we’ve talked about positive integers and how they’re represented in our machines. Yet, sometimes we need to work with negative numbers as well. How are they represented in the computers?
We’ve seen that the number 1 is represented as `0001` in binary, number 6 is represented as `0110`, etc. 0 is represented as all zeros `0000`. A logical trick we can do to store negative numbers is by keeping a “special” bit which would represent whether or not the number is negative. So, it would be 1 if the number is negative and 0 otherwise. And that’s exactly how most computers operate with negative numbers. They just have a special bit at the very left of the binary representation which is set to 1 if the number is negative and is set to 0 if it’s a positive one.
There is a bit more to it than just having 1 as the first bit in the binary representation. In decimal representation (our usual numbers like 4, 5, 10, 311, etc) negative and positive numbers cancel each other out. Adding 6 and -6 would result in 0. This property should not be lost in binary as well. So, if we add 6 and -6 in binary, we should get 0.
Imagine we have 4 bits to represent a number and a single bit to store the sign. So, there are 5 bits in total. So, 6 will be represented as `00110`, while 0 will be represented as `00000`. The binary representation of -6 should be the opposite of 6 so that the sum results in 0. Jumping a bit ahead, the representation of -6 would be `11010`. Therefore, if we add `00110` and `11010` in binary, it will result in `00000`.
To switch from positive to negative and back in binary, we can use a simple trick of flipping all the bits (all the 0s to 1s and all the 1s to 0s) and then adding 1 to the resulting number.
``````x = 6       # 00110
x = ~x + 1  # Flip all the bits and add 1 => -6
x = ~x + 1  # Flip all the bits and add 1 => 6

z = 0       # 00000
z = ~z + 1  # Flip and +1 => 0
z = ~z + 1  # Flip and +1 => 0
z = ~z      # -1  (all 1s in the binary representation)
z = ~z      # 0   (all 0s in the binary representation)``````
Note that adding a number in binary is the same as you’d add a number in decimal from the least significant digit to the most significant (along with keeping the carry number).
Depending on the language and implementation, computers store the numbers differently. Languages like C++ and Java have different types for different ranges of numbers. The type `int` stores integers in 32 bits: 31 bits for the number and the front bit for the sign ⇒ the numbers can range from `-2,147,483,648` () to `2,147,483,647` (). Note that the positives are less than one. This is due to the fact that positives start with a 0-bit and the first number that starts with a 0-bit is 0 itself (all 0s).

### Challenge

In the magical land of 7s, everything is aligned to have something related to the number 7. So, in this land computer scientists have developed a system where they store their binary numbers in 77 bits (both positive and negative).
Given a bit-string `b`, you are asked to calculate the negative value of that number and represent it in 77 bits.

#### Input

The input contains a single line representing the bit-string `b` (1 ≤ |b| ≤ 77). It can represent both a positive and a negative number.

#### Output

The output should contain a single line representing `-b` with length 77.

#### Examples

 Input Output 1 11111111111111111111111111111111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111111111111111111111111111111 00000000000000000000000000000000000000000000000000000000000000000000000000001

#### Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB