ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

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.
  1. All integers from 0 to 2n − 1 are written.
  2. Each integer x is replaced by F(x, n).
  3. 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).
  4. 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

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