2004. Scientists from Spilkovo @ Timus Online Judge

2004. Scientists from Spilkovo

Time limit: 0.5 second
Memory limit: 64 MB

Misha and Dima are promising young scientists. They make incredible discoveries every day together with their colleagues in the Spilkovo innovative center. Now Misha and Dima are studying the properties of an amazing function F which is written as follows.

C++:

int F(int x, int n)
{
    return (((x & ((1 << (n / 2)) - 1)) << ((n + 1) / 2)) | (x >> (n / 2)));
}

Pascal:

function F(x, n: integer): integer;
begin
    F := (((x and ((1 shl (n div 2)) - 1)) shl ((n + 1) div 2)) or (x shr (n div 2)));
end;

The friends want to perform the following computational experiment.

All integers from 0 to 2ⁿ − 1 are written.
Each integer x is replaced by F(x, n).
Each integer obtained after step 2 is written as a binary string of length n (if the integer has less than n bits, some leading zeroes are added; if the integer has more than n bits, only last n bits are written).
The result of the experiment is a binary string of minimum length, that contains all the strings obtained after step 3 as its substrings.

If you can perform this experiment, maybe you are able to work in Spilkovo too!

Input

The only line contains an integer n (1 ≤ n ≤ 20).

Output

Output the required binary string. If there are several optimal solutions, you may output any of them.

Sample

input	output
1	10

Problem Author: Ilya Kuchumov
Problem Source: Ural Regional School Programming Contest 2013