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.
int F(int x, int n)
return (((x & ((1 << (n / 2)) - 1)) << ((n + 1) / 2)) | (x >> (n / 2)));
function F(x, n: integer): integer;
F := (((x and ((1 shl (n div 2)) - 1)) shl ((n + 1) div 2)) or (x shr (n div 2)));
The friends want to perform the following computational experiment.
- All integers from 0 to 2n − 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
If you can perform this experiment, maybe you are able to work in Spilkovo too!
The only line contains an integer n (1 ≤ n ≤ 20).
Output the required binary string. If there are several optimal solutions,
you may output any of them.
Problem Author: Ilya Kuchumov
Problem Source: Ural Regional School Programming Contest 2013