시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB140221514.851%

문제

  시작 곡선 변형 1 변형 2 변형 3 변형 4
H1
H2
H3
H4

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

힐베르트 곡선은 가로줄과 세로줄로 이루어져 있는 곡선의 수열 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)을 잇는다.

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

그림 1 그림 2
H3과 수평선(2/8,7/8)-(7/8,7/8)은 3번 교차한다 H4과 수평선(0/16,1/16)-(16/16,1/16)은 16번 교차한다

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과 주어진 수평선과 교차하는 점의 개수를 출력한다.

예제 입력 1

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

예제 출력 1

3
16
1073741822
W3sicHJvYmxlbV9pZCI6IjQ2NDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3OTBcdWJjYTBcdWI5NzRcdWQyYjggXHVhY2UxXHVjMTIwIiwiZGVzY3JpcHRpb24iOiI8dGFibGUgY2xhc3M9XCJ0YWJsZVwiIHN0eWxlPVwid2lkdGg6NjcwcHg7XCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoyMHB4O3RleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdCZuYnNwOzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoxMzBweDt0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHRcdWMyZGNcdWM3OTEgXHVhY2UxXHVjMTIwPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEzMHB4O3RleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdFx1YmNjMFx1ZDYxNSAxPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEzMHB4O3RleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdFx1YmNjMFx1ZDYxNSAyPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEzMHB4O3RleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdFx1YmNjMFx1ZDYxNSAzPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEzMHB4O3RleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdFx1YmNjMFx1ZDYxNSA0PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGhlYWQ+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ2ZXJ0aWNhbC1hbGlnbjogbWlkZGxlO1wiPlxyXG5cdFx0XHRcdEg8c3ViPjE8XC9zdWI+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2gxLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMjEuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2gyMi5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDIzLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMjQuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidmVydGljYWwtYWxpZ246IG1pZGRsZTtcIj5cclxuXHRcdFx0XHRIPHN1Yj4yPFwvc3ViPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMi5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDMxLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMzIuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2gzMy5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDM0LmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInZlcnRpY2FsLWFsaWduOiBtaWRkbGU7XCI+XHJcblx0XHRcdFx0SDxzdWI+MzxcL3N1Yj48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDMuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g0MS5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDQyLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oNDMuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g0NC5naWZcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ2ZXJ0aWNhbC1hbGlnbjogbWlkZGxlO1wiPlxyXG5cdFx0XHRcdEg8c3ViPjQ8XC9zdWI+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g0LmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oNTEuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g1Mi5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDUzLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oNTQuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cclxuXHRcdWQ3OTBcdWJjYTBcdWI5NzRcdWQyYjggXHVhY2UxXHVjMTIwXHVjNzQwIFx1YjNjNVx1Yzc3YyBcdWMyMThcdWQ1NTlcdWM3OTAgXHViMmU0XHViZTQ0XHViNGRjIFx1ZDc5MFx1YmNhMFx1Yjk3NFx1ZDJiOFx1YWMwMCBcdWNjOThcdWM3NGNcdWM3M2NcdWI4NWMgXHViYjE4XHVjMGFjXHVkNTVjIFx1YzVmMFx1YzE4ZCBcdWQ1MDRcdWI3OTlcdWQwYzggXHVhY2Y1XHVhYzA0IFx1Y2M0NFx1YzZjMCBcdWFjZTFcdWMxMjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDc5MFx1YmNhMFx1Yjk3NFx1ZDJiOCBcdWFjZTFcdWMxMjBcdWM3NDAgXHVhYzAwXHViODVjXHVjOTA0XHVhY2ZjIFx1YzEzOFx1Yjg1Y1x1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWNlMVx1YzEyMFx1Yzc1OCBcdWMyMThcdWM1ZjQgSDxzdWI+MTxcL3N1Yj4sIEg8c3ViPjI8XC9zdWI+LCBIPHN1Yj4zPFwvc3ViPiwgSDxzdWI+NDxcL3N1Yj4sIC4uLlx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjZTFcdWMxMjBcdWM3NDAgXHViMmU4XHVjNzA0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBbMCwgMV0gJnRpbWVzOyBbMCwgMV1cdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRIPHN1Yj4xPFwvc3ViPlx1Yzc0MCAoJmZyYWMxNDssICZmcmFjMzQ7KSwgKCZmcmFjMTQ7LCAmZnJhYzE0OyksICgmZnJhYzM0OywgJmZyYWMxNDspLCAoJmZyYWMzNDssICZmcmFjMzQ7KVx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVjMTM4IFx1YzEyMFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBIPHN1Yj5uPFwvc3ViPlx1Yzc0MCBIPHN1Yj5uLTE8XC9zdWI+XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWIyZTRcdWM3NGMgNFx1YWMwMFx1YzljMCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YzdhY1x1YWRjMFx1YzgwMVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MS4gSDxzdWI+bi0xPFwvc3ViPlx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjXHViOTdjIFx1YzgwOFx1YmMxOFx1YzczY1x1Yjg1YyBcdWM5MDRcdWM3NzhcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0Mi4gXHVhY2UxXHVjMTIwXHVjNzQ0ICgwLCAmZnJhYzEyOylcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViM2NjXHViOWIwIFx1YWNlMVx1YzEyMFx1Yzc0NCBcdWIzNTRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0My4geCA9ICZmcmFjMTI7XHViOTdjIFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWIzMDBcdWNlNmRcdWMyZGNcdWQwYTggXHVhY2UxXHVjMTIwXHVjNzQ0IFx1YjM1NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHQ0LiBtID0gJmZyYWMxMjs8c3VwPm4rMTxcL3N1cD5cdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWFjMDEgXHVhY2UxXHVjMTIwXHVjNzU4IFx1YjA1ZFx1YzgxMCAoJmZyYWMxMjsgLSBtLCAmZnJhYzEyOyAtIG0pIFx1YzY0MCAoJmZyYWMxMjsgKyBtLCAmZnJhYzEyOyAtIG0pLCAobSwgJmZyYWMxMjsgLSBtKSBcdWM2NDAgKG0sICZmcmFjMTI7ICsgbSksICgxIC0gbSwgJmZyYWMxMjsgLSBtKSBcdWM2NDAgKDEgLSBtLCAmZnJhYzEyOyArIG0pXHVjNzQ0IFx1Yzc4N1x1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMjE4XHVkM2M5XHVjMTIwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWNlMVx1YzEyMFx1YWNmYyBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVjODEwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzg1XHViODI1IFx1YzYwOFx1YzgxYyBcdWNjYWIgXHViYzg4XHVjOWY4XHVjNjQwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVhZGY4XHViOWJjXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlXCIgc3R5bGU9XCJ3aWR0aDo3MCU7XCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDozNSU7dGV4dC1hbGlnbjpjZW50ZXI7XCI+XHJcblx0XHRcdFx0XHVhZGY4XHViOWJjIDE8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MzUlO3RleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdFx1YWRmOFx1YjliYyAyPFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyO1wiPlxyXG5cdFx0XHRcdDxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDNsaW5lLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHQ8aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g0bGluZS5naWZcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHRIPHN1Yj4zPFwvc3ViPlx1YWNmYyBcdWMyMThcdWQzYzlcdWMxMjAoMlwvOCw3XC84KS0oN1wvOCw3XC84KVx1Yzc0MCAzXHViYzg4IFx1YWQ1MFx1Y2MyOFx1ZDU1Y1x1YjJlNDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjtcIj5cclxuXHRcdFx0XHRIPHN1Yj40PFwvc3ViPlx1YWNmYyBcdWMyMThcdWQzYzlcdWMxMjAoMFwvMTYsMVwvMTYpLSgxNlwvMTYsMVwvMTYpXHVjNzQwIDE2XHViYzg4IFx1YWQ1MFx1Y2MyOFx1ZDU1Y1x1YjJlNDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+XHJcblx0SDxzdWI+bjxcL3N1Yj5cdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWQ1NmRcdWMwYzEgMVwvMjxzdXA+bisxPFwvc3VwPlx1Yzc1OCBcdWQ2NDBcdWMyMTggXHViYzMwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWMyMThcdWQzYzlcdWMxMjBcdWM3NTggXHViMDVkXHVjODEwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWQ1NmRcdWMwYzEgMVwvMjxzdXA+bjxcL3N1cD5cdWM3NTggXHViYzMwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWQ1NmRcdWMwYzEgSDxzdWI+bjxcL3N1Yj5cdWM3NTggXHVjMTM4XHViODVjXHVjMTIwXHVhY2ZjIFx1YWQ1MFx1Y2MyOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzc0XHViMmU0LiBcdWFjMDEgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgSDxzdWI+bjxcL3N1Yj5cdWFjZmMgXHVjMjE4XHVkM2M5XHVjMTIwKHg8c3ViPjE8XC9zdWI+XC8yPHN1cD5uPFwvc3VwPiwgeVwvMjxzdXA+bjxcL3N1cD4pLSh4PHN1Yj4yPFwvc3ViPlwvMjxzdXA+bjxcL3N1cD4sIHlcLzI8c3VwPm48XC9zdXA+KVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgNFx1YWMxY1x1Yzc1OCBcdWMyMTgobiB4PHN1Yj4xPFwvc3ViPiB4PHN1Yj4yPFwvc3ViPiB5KVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDAgJmx0OyBuICZsdDsgMzEsIHg8c3ViPjE8XC9zdWI+ICZsdDsgeDxzdWI+MjxcL3N1Yj4pIHg8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgeVx1YjI5NCBcdWQ1NmRcdWMwYzEgWzAsIDI8c3VwPm48XC9zdXA+XSBcdWJjOTRcdWM3MDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjljOFx1YzljMFx1YjljOSBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgSDxzdWI+bjxcL3N1Yj5cdWFjZmMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxOFx1ZDNjOVx1YzEyMFx1YWNmYyBcdWFkNTBcdWNjMjhcdWQ1NThcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNDY0NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhpbGJlcnQgQ3VydmUgSW50ZXJzZWN0aW9ucyIsImRlc2NyaXB0aW9uIjoiPHRhYmxlIGNsYXNzPVwidGFibGVcIiBzdHlsZT1cIndpZHRoOjY3MHB4XCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MjBweFwiPiZuYnNwOzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MTMwcHhcIj5TdGFydGluZyBjdXJ2ZTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MTMwcHhcIj5UcmFuc2Zvcm1hdGlvbiAxPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDoxMzBweFwiPlRyYW5zZm9ybWF0aW9uIDI8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXI7IHdpZHRoOjEzMHB4XCI+VHJhbnNmb3JtYXRpb24gMzxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MTMwcHhcIj5UcmFuc2Zvcm1hdGlvbiA0PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGhlYWQ+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ2ZXJ0aWNhbC1hbGlnbjptaWRkbGVcIj5IPHN1Yj4xPFwvc3ViPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMS5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDIxLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMjIuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2gyMy5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDI0LmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cInZlcnRpY2FsLWFsaWduOm1pZGRsZVwiPkg8c3ViPjI8XC9zdWI+PFwvdGQ+XHJcblx0XHRcdDx0ZD48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2gyLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMzEuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2gzMi5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDMzLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oMzQuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidmVydGljYWwtYWxpZ246bWlkZGxlXCI+SDxzdWI+MzxcL3N1Yj48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDMuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g0MS5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDQyLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oNDMuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g0NC5naWZcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ2ZXJ0aWNhbC1hbGlnbjptaWRkbGVcIj5IPHN1Yj40PFwvc3ViPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oNC5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDUxLmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0XHQ8dGQ+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oNTIuZ2lmXCIgXC8+PFwvdGQ+XHJcblx0XHRcdDx0ZD48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g1My5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkPjxpbWcgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaDU0LmdpZlwiIFwvPjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+RGF2aWQgSGlsYmVydCBwcm92ZWQgdGhlIGV4aXN0ZW5jZSBvZiBhIHZlcnkgY291bnRlci1pbnR1aXRpdmUgY3VydmUgdGhhdCBmaWxscyBzcGFjZS4gVGhlIGNvbnN0cnVjdGlvbiBvZiB0aGUgSGlsYmVydCBjdXJ2ZSBpcyBiYXNlZCBvbiBhIHNlcXVlbmNlIG9mIGN1cnZlcywgSDxzdWI+MTxcL3N1Yj4sIEg8c3ViPjI8XC9zdWI+LCBIPHN1Yj4zPFwvc3ViPiwgSDxzdWI+NDxcL3N1Yj4sIC4uLiBjb21wb3NlZCBvZiBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBzZWdtZW50cy4gRWFjaCBjdXJ2ZSBsaWVzIGluIHRoZSB1bml0IHNxdWFyZSBbMCwgMV0gJnRpbWVzOyBbMCwgMV0uIEg8c3ViPjE8XC9zdWI+IGNvbnRhaW5zIGp1c3QgdGhyZWUgc2VnbWVudHMsIGNvbm5lY3RpbmcgdGhlIHBvaW50cyAoJmZyYWMxNDssICZmcmFjMzQ7KSB0byAoJmZyYWMxNDssICZmcmFjMTQ7KSB0byAoJmZyYWMzNDssICZmcmFjMTQ7KSB0byAoJmZyYWMzNDssICZmcmFjMzQ7KS4gSG4gaXMgZGVmaW5lZCByZWN1cnNpdmVseSBpbiB0ZXJtcyBvZiBIbi0xLCBmb3IgbiA9IDIsIDMsIC4uLiBieSBmb3VyIHRyYW5zZm9ybWF0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5IYWx2ZSBhbGwgY29vcmRpbmF0ZXMgaW4gSDxzdWI+bi0xPFwvc3ViPi48XC9saT5cclxuXHQ8bGk+QWRkIGEgY29weSByb3RhdGVkIDkwIGRlZ3JlZXMgY291bnRlcmNsb2Nrd2lzZSBhYm91dCB0aGUgcG9pbnQgKDAsICZmcmFjMTI7KS48XC9saT5cclxuXHQ8bGk+QWRkIHRoZSByZWZsZWN0aW9uIGFjcm9zcyB0aGUgbGluZSB4ID0gJmZyYWMxMjsuPFwvbGk+XHJcblx0PGxpPkxldCBtID0gJmZyYWMxMjs8c3VwPm4rMTxcL3N1cD4uIEFkZCBzZWdtZW50cyBjb25uZWN0aW5nIGVuZHBvaW50cyAoJmZyYWMxMjsgLSBtLCAmZnJhYzEyOyAtIG0pIHRvICgmZnJhYzEyOyArIG0sICZmcmFjMTI7IC0gbSksIChtLCAmZnJhYzEyOyAtIG0pIHRvIChtLCAmZnJhYzEyOyArIG0pLCBhbmQgKDEgLSBtLCAmZnJhYzEyOyAtIG0pIHRvICgxIC0gbSwgJmZyYWMxMjsgKyBtKS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3VyIGpvYiBpcyB0byBjb3VudCB0aGUgbnVtYmVyIG9mIGludGVyc2VjdGlvbnMgb2YgaG9yaXpvbnRhbCBsaW5lIHNlZ21lbnRzIHdpdGggdGhlc2UgY3VydmVzLiBGb3IgZXhhbXBsZSwgY29uc2lkZXIgRmlndXJlcyAxIGFuZCAyLCB3aGljaCBpbGx1c3RyYXRlIHRoZSBmaXJzdCB0d28gZXhhbXBsZSBpbnB1dCBkYXRhIHNldHMgYmVsb3cuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlXCIgc3R5bGU9XCJ3aWR0aDo3MCVcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDozNSVcIj5GaWd1cmUgMTxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MzUlXCI+RmlndXJlIDI8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2gzbGluZS5naWZcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2g0bGluZS5naWZcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlNlZ21lbnQgZnJvbSAoMlwvOCwgN1wvOCkgdG8gKDdcLzgsIDdcLzgpIGNyb3NzaW5nIEg8c3ViPjM8XC9zdWI+IHRocmVlIHRpbWVzLjxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlNlZ21lbnQgZnJvbSAoMFwvMTYsIDFcLzE2KSB0byAoMTZcLzE2LCAxXC8xNikgY3Jvc3NpbmcgSDxzdWI+NDxcL3N1Yj4gc2l4dGVlbiB0aW1lcy48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlRoZSBjb29yZGluYXRlcyBvZiB2ZXJ0aWNlcyBvZiBIbiBhcmUgb2RkIG11bHRpcGxlcyBvZiAmZnJhYzEyOzxzdXA+bisxPFwvc3VwPi4gVGhlIGNvb3JkaW5hdGVzIG9mIGhvcml6b250YWwgc2VnbWVudCBlbmRwb2ludHMgd2lsbCBhbHdheXMgYmUgbXVsdGlwbGVzIG9mICZmcmFjMTI7PHN1cD5uPFwvc3VwPi4gSGVuY2UgdGhlIHNwZWNpZmllZCBob3Jpem9udGFsIHNlZ21lbnQgY2FuIG9ubHkgY3Jvc3MgdmVydGljYWwgc2VnbWVudHMgaW4gSDxzdWI+bjxcL3N1Yj4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiBvbmUgdG8gMTAwIGRhdGEgc2V0cywgb25lIHBlciBsaW5lLCBmb2xsb3dlZCBieSBhIGZpbmFsIGxpbmUgY29udGFpbmluZyBvbmx5IDAuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgZm91ciBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYmxhbmtzIGluIHRoZSBmb3JtPFwvcD5cclxuXHJcbjxwcmU+XHJcbm4geDxzdWI+MTxcL3N1Yj4geDxzdWI+MjxcL3N1Yj4geTxcL3ByZT5cclxuXHJcbjxwPndoaWNoIHJlcHJlc2VudHMgSDxzdWI+bjxcL3N1Yj4gYW5kIHRoZSBzZWdtZW50IGZyb20gKHg8c3ViPjE8XC9zdWI+XC8yPHN1cD5uPFwvc3VwPiwgeVwvMjxzdXA+bjxcL3N1cD4pIHRvICh4PHN1Yj4yPFwvc3ViPlwvMjxzdXA+bjxcL3N1cD4sIHlcLzI8c3VwPm48XC9zdXA+KSwgd2hlcmUgMCAmbHQ7IG4gJmx0OyAzMSwgeDxzdWI+MTxcL3N1Yj4gJmx0OyB4PHN1Yj4yPFwvc3ViPiwgYW5kIGVhY2ggb2YgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCBhbmQgeSBsaWUgaW4gdGhlIHJhbmdlIDAgdG8gMjxzdXA+bjxcL3N1cD4sIGluY2x1c2l2ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGlzIG9uZSBpbnRlZ2VyIHBlciBsaW5lIGZvciBlYWNoIGRhdGEgc2V0OiB0aGUgbnVtYmVyIG9mIGludGVyc2VjdGlvbnMgb2YgSDxzdWI+bjxcL3N1Yj4gd2l0aCB0aGUgc2VnbWVudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Q2F1dGlvbjogQSBicnV0ZSBmb3JjZSBzb2x1dGlvbiB0aGF0IGNvbXB1dGVzIGVhY2ggaW50ZXJzZWN0aW9uIGluZGl2aWR1YWxseSB3aWxsIG5vdCBmaW5pc2ggd2l0aGluIHRoZSBvbmUgbWludXRlIHRpbWUgbGltaXQuIEFzIHlvdSBjYW4gc2VlIGJlbG93LCB0aGVyZSBtYXkgYmUgbW9yZSB0aGFuIG9uZSBiaWxsaW9uIGludGVyc2VjdGlvbnMgZm9yIGFueSBkYXRhIHNldDxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > Mid-Central Regional > 2002 Mid-Central Regional Programming Contest B번