Problem A. Alternating Binary Sequence ≡

Statement

Let there be an infinite sequence of binary strings s[1], s[2], s[3], …. Each string is obtained as follows:

For each k, string s[k] is a concatenation of altering blocks of digits.

In particular:

• If k is odd then the string starts with 0, followed by 1, then 0, then 11, then 0, then 111, and so on. Thus, each block of ones is one symbol longer than the previous one. The total length of the string is equal to k.
• If k is even then the string starts with 1, followed by 0, then 1, then 00, then 1, then 000, and so on. Thus, each block of zeros is one symbol longer than the previous one. The total length of the string is equal to k.

The first 10 strings are:

0
10
010
1010
01011
101001
0101101
10100100
010110111 
1010010001

Given an integer n find and output the string s[n].

Input format

The first line of the input contains a single integer n.

Output format

Output a single string of length n as described in the problem statement.

Constraints

1 ≤ n ≤ 10⁵

Sample tests

1

0

5

01011

11

01011011101