힐베르트 곡선

힐베르트 곡선은 독일 수학자 다비드 힐베르트가 처음으로 묘사한 연속 프랙탈 공간 채움 곡선이다.

힐베르트 곡선은 가로줄과 세로줄로 이루어져 있는 곡선의 수열 H1, H2, H3, H4, ...을 이용해서 만들 수 있다. 각각의 곡선은 단위 정사각형 [0, 1] × [0, 1]위에 있다.

H1은 (¼, ¾), (¼, ¼), (¾, ¼), (¾, ¾)을 잇는 세 선분으로 이루어져 있다. Hn은 Hn-1을 이용해서 다음 4가지 과정을 통해서 재귀적으로 만들 수 있다.

1. Hn-1의 모든 좌표를 절반으로 줄인다.

2. 곡선을 (0, ½)을 기준으로 반시계 방향으로 돌린 곡선을 더한다.

3. x = ½를 기준으로 대칭시킨 곡선을 더한다.

4. m = ½n+1이라 하자. 각 곡선의 끝점 (½ - m, ½ - m) 와 (½ + m, ½ - m), (m, ½ - m) 와 (m, ½ + m), (1 - m, ½ - m) 와 (1 - m, ½ + m)을 잇는다.

수평선이 주어졌을 때, 곡선과 교차하는 점의 수를 구하는 프로그램을 작성하시오. 예를 들어, 입력 예제 첫 번째와 두 번째 그림은 다음과 같다.

Hn의 꼭짓점 좌표는 항상 1/2n+1의 홀수 배수이다. 수평선의 끝점 좌표는 항상 1/2n의 배수이다. 따라서, 선분은 항상 Hn의 세로선과 교차한다.

입력은 여러 개의 데이터로 이루어져 있다. 주어지는 데이터는 최대 100개이다. 각 데이터는 다음과 같은 Hn과 수평선(x1/2n, y/2n)-(x2/2n, y/2n)을 나타내는 4개의 수(n x1 x2 y)가 공백으로 구분되어져 있다. (0 < n < 31, x1 < x2) x1, x2, y는 항상 [0, 2n] 범위이다.

마지막 데이터의 다음 줄에는 0이 하나 주어진다.

각 데이터에 대해서 Hn과 주어진 수평선과 교차하는 점의 개수를 출력한다.