Negation and complement of a number

When working with binary numbers it’s sometimes necessary to flip the bits (turn all the 1s to 0s and all the 0s to 1s). This is called computing the complement or the negation of a number.
Given an integer n, you are asked to calculate its negation (flip the bits).

Input

The input contains a single integer n (1 ≀ n ≀ ).

Output

The program should print the binary negation of n. The negation should start from 0 (the leftmost 1 in the binary representation of n).

Examples

Input
Output
6
001
311
011001000

Explanation

  • 6: 110 β‡’ negation will be 001
  • 311: 100110111 β‡’ negation will be 011001000
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue