Hilbert Curve

Time limit1sMemory limit128 MB

Summary

Count how many points the n-th Hilbert curve shares with a given horizontal segment whose endpoints are grid multiples of 1/2^n.

Level: Hard8 of 10
Topics: Recursion, Divide and conquer, Geometry, Implementation
Solved: No attempts yet

Problem

The Hilbert curve is a continuous, space-filling fractal curve first described by the German mathematician David Hilbert.

It is defined through a sequence of curves $H_1, H_2, H_3, \dots$ , each made of horizontal and vertical segments. Every curve lies inside the unit square $[0, 1] \times [0, 1]$ .

$H_1$ consists of the three segments that connect the four points $(\frac{1}{4}, \frac{3}{4})$ , $(\frac{1}{4}, \frac{1}{4})$ , $(\frac{3}{4}, \frac{1}{4})$ , $(\frac{3}{4}, \frac{3}{4})$ in order.

$H_n$ is built recursively from $H_{n-1}$ through the following four steps.

Halve every coordinate of $H_{n-1}$ .
Add a copy of that curve rotated $90^\circ$ counterclockwise about the point $(0, \frac{1}{2})$ .
Add a copy of the curve obtained so far, reflected across the line $x = \frac{1}{2}$ .
Let $m = \frac{1}{2^{n+1}}$ . Join the pieces with three segments: connect $(\frac{1}{2} - m, \frac{1}{2} - m)$ with $(\frac{1}{2} + m, \frac{1}{2} - m)$ , connect $(m, \frac{1}{2} - m)$ with $(m, \frac{1}{2} + m)$ , and connect $(1 - m, \frac{1}{2} - m)$ with $(1 - m, \frac{1}{2} + m)$ .

Given a horizontal segment, write a program that counts how many points it shares with the curve. For example, $H_3$ meets the horizontal segment $(\frac{2}{8}, \frac{7}{8})$ – $(\frac{7}{8}, \frac{7}{8})$ at $3$ points, and $H_4$ meets the horizontal segment $(\frac{0}{16}, \frac{1}{16})$ – $(\frac{16}{16}, \frac{1}{16})$ at $16$ points.

The vertex coordinates of $H_n$ are always odd multiples of $\frac{1}{2^{n+1}}$ , while the endpoint coordinates of the horizontal segment are always multiples of $\frac{1}{2^{n}}$ . Consequently the horizontal segment only ever meets the vertical parts of $H_n$ .

Input

The input consists of several datasets (test cases), at most $100$ of them.

Each dataset is given as four space-separated integers $n$ , $x_1$ , $x_2$ , $y$ , describing the curve $H_n$ and the horizontal segment $(\frac{x_1}{2^n}, \frac{y}{2^n})$ – $(\frac{x_2}{2^n}, \frac{y}{2^n})$ . Here $0 < n < 31$ and $x_1 < x_2$ , and $x_1$ , $x_2$ , $y$ are all integers in the range $[0, 2^n]$ .

A single line containing $0$ follows the last dataset and marks the end of the input.

Output

For each dataset, print on its own line the number of points where the curve $H_n$ meets the given horizontal segment.

Examples6

Example 1

Input

3 2 7 7
4 0 16 1
30 1 1073741823 1
0

Expected output

3
16
1073741822

Example 2
Input
```
1 0 2 1
0
```
Expected output
```
2
```
Example 3
Input
```
2 0 4 1
2 0 4 2
2 0 4 3
0
```
Expected output
```
4
2
2
```
Example 4
Input
```
3 0 8 0
3 0 8 8
0
```
Expected output
```
0
0
```
Example 5
Input
```
4 0 16 8
4 3 5 8
0
```
Expected output
```
2
0
```
Example 6
Input
```
3 3 4 5
3 0 1 5
3 1 3 3
0
```
Expected output
```
1
1
2
```