Submit solution

Points: 5 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

One of ButaneBot's intended functions is to perform an OR-sum on a large range of numbers. More specifically, ButaneBot should be able to read in a number N, compute 1 \mathbin{|} 2 \mathbin{|} \dots \mathbin{|} N, and output that number in base 2. However, whenever ButaneBot tries to execute his OR-sum function, he malfunctions and explodes. Can you help ButaneBot by recoding this function?

Reminder: A bitwise OR takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1.

For example

    0101 (decimal 5)
 OR 0011 (decimal 3)
  = 0111 (decimal 7)

Input Specification

The only line of input will contain a single integer N.


Subtask 1 [40%]

N \le 500\,000\,000

Subtask 2 [60%]

N \le 10^{10}

Output Specification

Output the OR-sum from 1 to N as a binary number.

Sample Input


Sample Output


Explanation for Sample Output

The OR-sum from 1 to 1 is simply 1. 1 in binary is once again 1.

Note: The input will overflow an integer in some languages.


  • 2
    discoverMe  commented on March 17, 2018, 8:09 p.m.

    the input is in base 10 btw