Practice Strings and Fractal with the exercise "Paper-folding curve"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Strings

Statement

Goal

Get a stripe of paper. Fold it into half. Fold it into half again in the same direction. Fold it the third time into half, in the same direction. Then open it, so that every fold is at a right angle. Viewing it from the edge you could see a pattern like this:

   _ 
|_| |_
     _|

Since we made 3 folds to create this curve, we call it an order-3 curve.

Following the same procedure we can arrive at different orders of the curve.
order-1

_|

order-2

   _
|_|

order-3

 _
|_   _
  |_| |

order-4

   _   _
  |_|_| |_
   _|    _|
|_|

The curve can expand to infinite orders.

If you follow one end of the curve to go along the path, you will meet either LEFT or RIGHT turns. We write LEFT as 1, and RIGHT as 0. We describe a curve by a sequence of 0 and 1.

Depending on which end you are viewing the paper, and from which end you start walking through the path, the same curve can be represented in four different ways. We arbitrarily choose one as the "correct" representation:

The sequence of order-1 curve is: 1
The sequence of order-2 curve is: 110
The sequence of order-3 curve is: 1101100

Your task is to find the Sequence of higher order curves using the same representation scheme as above.

Input

Line 1 An integer N for the order of the curve
Line 2 A starting index and an ending index (both 0-based and inclusive) of a sub-string of the Sequence

Output

You do not need to output the full sequence. You only need to output a sub-Sequence as defined above.

Constraints

1 ≤ N ≤ 50
ending index - starting index ≤ 255
starting index, ending index ≤ 1,000,000,000,000,000

Example

Input

3
3 6

Output

Solve it

A higher resolution is required to access the IDE