시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 1 1 100.000%

문제

칼리가 살던 곳의 문명은 우리의 문명과는 다르지만 그 곳도 정부, 기업, 기술을 가지고 있었다. 가장 큰 차이는 세율의 결정 방법이었다. 그들은 흥정하는 것을 좋아했기 때문에 세율도 흥정으로 결정하였다. 

세금 계약을 작성할 때, 정부 관료들과 흥정하기 위해 수도로 가야한다. 계약에는 시작일, 만기일, 세율에 관한 내용이 있다. (부기 때문에 만기일은 항상 마지막달의 15일이다.) 계약 마지막 달과 새 계약이 시작하기 전 동안의 짧은 세금이 없는 기간을 즐기는 것은 칼리 가족의 전통이다. 이 기간 역시 흥정을 할 때이기도 하다.

칼리가 살던 곳은 매우 번영하고 인구가 많아서 정부 관료들은 업무가 매우 많았다. 세금 흥정 거래가 성사되면 관료들은 속기로 써서 일이 진행될 수 있도록 전달한다. 이 속기 노트를 컴퓨터로 입력하려면 XML 형식으로 전환되어야 한다. 때때로 노트가 완성된 게 아니라 세금 계약을 하러 다시 수도로 사람이 불려오기도 했다. 이 일련의 과정은 굉장히 비효율적이지만 이 방식은 이 곳 사람들이 하던 방식이고, 그 방법을 바꿀 생각이 없다.

노트를 XML 형식으로 바꾸는 프로그램을 작성하시오.

입력

입력은 여러개의 데이터 세트로 구성되어 있으며, 각 세트는 한 줄로 구성되어 있다.

각 줄은 3개의 정보로 구성되어 있다.

  1. 세율
    • 세율은 숫자 뒤에 %가 붙어있다. (예 5%)
    • 소수점이 없다.
    • 세율은 분수가 될 수 있지만 분모는 2,4,8 중에 하나이다.
    • 세율은 분자가 분모보다 작다.
  2. 계약 종료 날짜
    • 계약이 끝나는 달과 연도의 두자리로 들어온다. 두 숫자는 붙어서 들어오거나 하이픈으로 연결되어 있다. 예를 들어, 12-05 또는 1205는 05년 12월 15일을 뜻한다.
  3. 계약 시작 날짜
    • 종료 날짜와 마찬가지 형식이며, 현재 날짜보다 이후로 간주한다.

3개의 정보는 0개 이상의 공백으로 구분되어 있다.

달력은 우리와 같이 12개의 달로 구성되어 있지만, 모든 달은 31일까지 있다.

최고 세율은 99.875%이다.

출력

각 데이터 세트에 대해 들여쓰기를 올바르게 한 XML을 출력한다. (들여쓰기 하나는 4개의 공백)

<Kalii Index=N>
    <startdate><start date)</startdate>
    <rate>(tax rate)</rate>
    <enddate>(end date)</enddate>
</Kalii>

N은 데이터 세트 번호이며, (start date)는 시작일, (tax rate)는 세율, (end date)는 종료일을 뜻한다.

데이터가 잘못되었거나 모호하여 출력할 수 없으면

<Kalii Index=N>BAD INPUT</Kalii> 라고 출력한다. (N은 데이터 세트 번호)

시작일은 DDMMMYY 형태이며, 종료일은 15MMMYY이다.

DD는 01-31, MMM은 JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC로 구성되어 있다. YY는 00-99로 구성되어 있다.

세율은 소수점 3자리까지 정확해야 한다.

예제 입력 1

25/850812-31
6%     02110122
6.75% 2-11 4-23

예제 출력 1

<Kalii Index=1>
    <startdate>31DEC03</startdate>
    <rate>2.625</rate>
    <enddate>15MAY08</enddate>
</Kalii>
<Kalii Index=2>
    <startdate>22JAN04</startdate>
    <rate>6.000</rate>
    <enddate>15FEB11</enddate>
</Kalii>
<Kalii Index=3>BAD DATA</Kalii>
W3sicHJvYmxlbV9pZCI6IjI3NjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzhcdWFlMDggXHVhY2M0XHVjMGIwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNlN2NcdWI5YWNcdWFjMDAgXHVjMGI0XHViMzU4IFx1YWNmM1x1Yzc1OCBcdWJiMzhcdWJhODVcdWM3NDAgXHVjNmIwXHViOWFjXHVjNzU4IFx1YmIzOFx1YmE4NVx1YWNmY1x1YjI5NCBcdWIyZTRcdWI5NzRcdWM5YzBcdWI5Y2MgXHVhZGY4IFx1YWNmM1x1YjNjNCBcdWM4MTVcdWJkODAsIFx1YWUzMFx1YzVjNSwgXHVhZTMwXHVjMjIwXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjYzI4XHVjNzc0XHViMjk0IFx1YzEzOFx1YzcyOFx1Yzc1OCBcdWFjYjBcdWM4MTUgXHViYzI5XHViYzk1XHVjNzc0XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVkNzY1XHVjODE1XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzEzOFx1YzcyOFx1YjNjNCBcdWQ3NjVcdWM4MTVcdWM3M2NcdWI4NWMgXHVhY2IwXHVjODE1XHVkNTU4XHVjNjAwXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWMxMzhcdWFlMDggXHVhY2M0XHVjNTdkXHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU2MCBcdWI1NGMsIFx1YzgxNVx1YmQ4MCBcdWFkMDBcdWI4Y2NcdWI0ZTRcdWFjZmMgXHVkNzY1XHVjODE1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMyMThcdWIzYzRcdWI4NWMgXHVhYzAwXHVjNTdjXHVkNTVjXHViMmU0LiBcdWFjYzRcdWM1N2RcdWM1ZDBcdWIyOTQgXHVjMmRjXHVjNzkxXHVjNzdjLCBcdWI5Y2NcdWFlMzBcdWM3N2MsIFx1YzEzOFx1YzcyOFx1YzVkMCBcdWFkMDBcdWQ1NWMgXHViMGI0XHVjNmE5XHVjNzc0IFx1Yzc4OFx1YjJlNC4gKFx1YmQ4MFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViOWNjXHVhZTMwXHVjNzdjXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWI5YzhcdWM5YzBcdWI5YzlcdWIyZWNcdWM3NTggMTVcdWM3N2NcdWM3NzRcdWIyZTQuKSBcdWFjYzRcdWM1N2QgXHViOWM4XHVjOWMwXHViOWM5IFx1YjJlY1x1YWNmYyBcdWMwYzggXHVhY2M0XHVjNTdkXHVjNzc0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMCBcdWM4MDQgXHViM2Q5XHVjNTQ4XHVjNzU4IFx1YzllN1x1Yzc0MCBcdWMxMzhcdWFlMDhcdWM3NzQgXHVjNWM2XHViMjk0IFx1YWUzMFx1YWMwNFx1Yzc0NCBcdWM5OTBcdWFlMzBcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Y2U3Y1x1YjlhYyBcdWFjMDBcdWM4NzFcdWM3NTggXHVjODA0XHVkMWI1XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhZTMwXHVhYzA0IFx1YzVlZFx1YzJkYyBcdWQ3NjVcdWM4MTVcdWM3NDQgXHVkNTYwIFx1YjU0Y1x1Yzc3NFx1YWUzMFx1YjNjNCBcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2U3Y1x1YjlhY1x1YWMwMCBcdWMwYjRcdWIzNTggXHVhY2YzXHVjNzQwIFx1YjllNFx1YzZiMCBcdWJjODhcdWM2MDFcdWQ1NThcdWFjZTAgXHVjNzc4XHVhZDZjXHVhYzAwIFx1YjljZVx1YzU0NFx1YzExYyBcdWM4MTVcdWJkODAgXHVhZDAwXHViOGNjXHViNGU0XHVjNzQwIFx1YzVjNVx1YmIzNFx1YWMwMCBcdWI5ZTRcdWM2YjAgXHViOWNlXHVjNTU4XHViMmU0LiBcdWMxMzhcdWFlMDggXHVkNzY1XHVjODE1IFx1YWM3MFx1Yjc5OFx1YWMwMCBcdWMxMzFcdWMwYWNcdWI0MThcdWJhNzQgXHVhZDAwXHViOGNjXHViNGU0XHVjNzQwIFx1YzE4ZFx1YWUzMFx1Yjg1YyBcdWMzNjhcdWMxMWMgXHVjNzdjXHVjNzc0IFx1YzljNFx1ZDU4OVx1YjQyMCBcdWMyMTggXHVjNzg4XHViM2M0XHViODVkIFx1YzgwNFx1YjJlY1x1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzE4ZFx1YWUzMCBcdWIxNzhcdWQyYjhcdWI5N2MgXHVjZWY0XHVkNGU4XHVkMTMwXHViODVjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjgyNFx1YmE3NCBYTUwgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzgwNFx1ZDY1OFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjU0Y1x1YjU0Y1x1Yjg1YyBcdWIxNzhcdWQyYjhcdWFjMDAgXHVjNjQ0XHVjMTMxXHViNDFjIFx1YWM4YyBcdWM1NDRcdWIyYzhcdWI3N2MgXHVjMTM4XHVhZTA4IFx1YWNjNFx1YzU3ZFx1Yzc0NCBcdWQ1NThcdWI3ZWMgXHViMmU0XHVjMmRjIFx1YzIxOFx1YjNjNFx1Yjg1YyBcdWMwYWNcdWI3OGNcdWM3NzQgXHViZDg4XHViODI0XHVjNjI0XHVhZTMwXHViM2M0IFx1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1Yzc3Y1x1YjgyOFx1Yzc1OCBcdWFjZmNcdWM4MTVcdWM3NDAgXHVhZDQ5XHVjN2E1XHVkNzg4IFx1YmU0NFx1ZDZhOFx1YzcyOFx1YzgwMVx1Yzc3NFx1YzljMFx1YjljYyBcdWM3NzQgXHViYzI5XHVjMmRkXHVjNzQwIFx1Yzc3NCBcdWFjZjMgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1ZDU1OFx1YjM1OCBcdWJjMjlcdWMyZGRcdWM3NzRcdWFjZTAsIFx1YWRmOCBcdWJjMjlcdWJjOTVcdWM3NDQgXHViYzE0XHVhZmMwIFx1YzBkZFx1YWMwMVx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE3OFx1ZDJiOFx1Yjk3YyBYTUwgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWMxMzhcdWQyYjhcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjOTA0XHVjNzQwIDNcdWFjMWNcdWM3NTggXHVjODE1XHViY2Y0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjMTM4XHVjNzI4XHJcblx0PHVsPlxyXG5cdFx0PGxpPlx1YzEzOFx1YzcyOFx1Yzc0MCBcdWMyMmJcdWM3OTAgXHViNGE0XHVjNWQwICVcdWFjMDAgXHViZDk5XHVjNWI0XHVjNzg4XHViMmU0LiAoXHVjNjA4IDUlKTxcL2xpPlxyXG5cdFx0PGxpPlx1YzE4Y1x1YzIxOFx1YzgxMFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0XHQ8bGk+XHVjMTM4XHVjNzI4XHVjNzQwIFx1YmQ4NFx1YzIxOFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYyBcdWJkODRcdWJhYThcdWIyOTQgMiw0LDggXHVjOTExXHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHRcdDxsaT5cdWMxMzhcdWM3MjhcdWM3NDAgXHViZDg0XHVjNzkwXHVhYzAwIFx1YmQ4NFx1YmFhOFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPlx1YWNjNFx1YzU3ZCBcdWM4ODVcdWI4Y2MgXHViMGEwXHVjOWRjXHJcblx0PHVsPlxyXG5cdFx0PGxpPlx1YWNjNFx1YzU3ZFx1Yzc3NCBcdWIwNWRcdWIwOThcdWIyOTQgXHViMmVjXHVhY2ZjIFx1YzVmMFx1YjNjNFx1Yzc1OCBcdWI0NTBcdWM3OTBcdWI5YWNcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWI0NTAgXHVjMjJiXHVjNzkwXHViMjk0IFx1YmQ5OVx1YzViNFx1YzExYyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFjNzBcdWIwOTggXHVkNTU4XHVjNzc0XHVkNTA4XHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDEyLTA1IFx1YjYxMFx1YjI5NCAxMjA1XHViMjk0IDA1XHViMTQ0IDEyXHVjNmQ0IDE1XHVjNzdjXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+XHVhY2M0XHVjNTdkIFx1YzJkY1x1Yzc5MSBcdWIwYTBcdWM5ZGNcclxuXHQ8dWw+XHJcblx0XHQ8bGk+XHVjODg1XHViOGNjIFx1YjBhMFx1YzlkY1x1YzY0MCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzAgXHVkNjE1XHVjMmRkXHVjNzc0XHViYTcwLCBcdWQ2MDRcdWM3YWMgXHViMGEwXHVjOWRjXHViY2Y0XHViMmU0IFx1Yzc3NFx1ZDZjNFx1Yjg1YyBcdWFjMDRcdWM4ZmNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+M1x1YWMxY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgMFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlY1x1YjgyNVx1Yzc0MCBcdWM2YjBcdWI5YWNcdWM2NDAgXHVhYzE5XHVjNzc0IDEyXHVhYzFjXHVjNzU4IFx1YjJlY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwXHViOWNjLCBcdWJhYThcdWI0ZTAgXHViMmVjXHVjNzQwIDMxXHVjNzdjXHVhZTRjXHVjOWMwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVhY2UwIFx1YzEzOFx1YzcyOFx1Yzc0MCA5OS44NzUlXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWI0ZTRcdWM1ZWNcdWM0ZjBcdWFlMzBcdWI5N2MgXHVjNjJjXHViYzE0XHViOTc0XHVhYzhjIFx1ZDU1YyBYTUxcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHViNGU0XHVjNWVjXHVjNGYwXHVhZTMwIFx1ZDU1OFx1YjA5OFx1YjI5NCA0XHVhYzFjXHVjNzU4IFx1YWNmNVx1YmMzMSk8XC9wPlxyXG5cclxuPHByZT5cclxuJmx0O0thbGlpIEluZGV4PU4mZ3Q7XHJcbiAgICAmbHQ7c3RhcnRkYXRlJmd0OyZsdDtzdGFydCBkYXRlKSZsdDtcL3N0YXJ0ZGF0ZSZndDtcclxuICAgICZsdDtyYXRlJmd0Oyh0YXggcmF0ZSkmbHQ7XC9yYXRlJmd0O1xyXG4gICAgJmx0O2VuZGRhdGUmZ3Q7KGVuZCBkYXRlKSZsdDtcL2VuZGRhdGUmZ3Q7XHJcbiZsdDtcL0thbGlpJmd0OzxcL3ByZT5cclxuXHJcbjxwPk5cdWM3NDAgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOCBcdWJjODhcdWQ2MzhcdWM3NzRcdWJhNzAsIChzdGFydCBkYXRlKVx1YjI5NCBcdWMyZGNcdWM3OTFcdWM3N2MsICh0YXggcmF0ZSlcdWIyOTQgXHVjMTM4XHVjNzI4LCAoZW5kIGRhdGUpXHViMjk0IFx1Yzg4NVx1YjhjY1x1Yzc3Y1x1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjM3MFx1Yzc3NFx1ZDEzMFx1YWMwMCBcdWM3OThcdWJhYmJcdWI0MThcdWM1YzhcdWFjNzBcdWIwOTggXHViYWE4XHVkNjM4XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTc0PFwvcD5cclxuXHJcbjxwPjxjb2RlPiZsdDtLYWxpaSBJbmRleD1OJmd0O0JBRCBJTlBVVCZsdDtcL0thbGlpJmd0OzxcL2NvZGU+IFx1Yjc3Y1x1YWNlMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChOXHVjNzQwIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjggXHViYzg4XHVkNjM4KTxcL3A+XHJcblxyXG48cD5cdWMyZGNcdWM3OTFcdWM3N2NcdWM3NDAgRERNTU1ZWSBcdWQ2MTVcdWQwZGNcdWM3NzRcdWJhNzAsIFx1Yzg4NVx1YjhjY1x1Yzc3Y1x1Yzc0MCAxNU1NTVlZXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5ERFx1YjI5NCAwMS0zMSwgTU1NXHVjNzQwIEpBTixGRUIsTUFSLEFQUixNQVksSlVOLEpVTCxBVUcsU0VQLE9DVCxOT1YsREVDXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFlZXHViMjk0IDAwLTk5XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOFx1YzcyOFx1Yzc0MCBcdWMxOGNcdWMyMThcdWM4MTAgM1x1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWM4MTVcdWQ2NTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3NjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUYXhhdGlvbiBXaXRoIFJlcHJlc2VudGF0aW9uIE92ZXJkb25lIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgbGFuZCBvZiBLYWxpaSBsaXZlZCBhIGNpdmlsaXphdGlvbiBub3QgdW5saWtlIG91ciBvd24uIFRoZXkgaGFkIGdvdmVybm1lbnQsIGJ1c2luZXNzLCBhbmQgdGVjaG5vbG9neS4gVGhlIG9ubHkgbWFqb3IgZGlmZmVyZW5jZSB3YXMgaG93IHRheCByYXRlcyB3ZXJlIGRlY2lkZWQuIFlvdSBzZWUsIHRoZSBwZW9wbGUgb2YgS2FsaWkgbG92ZWQgdG8gaGFnZ2xlLiBUaGV5IGhhZ2dsZWQgb3ZlciBldmVyeXRoaW5nIGluY2x1ZGluZyB3aGF0IHBlcmNlbnRhZ2Ugb2YgdGhlaXIgaW5jb21lIHdlbnQgdG8gdGhlIGdvdmVybm1lbnQgY29mZmVycy4gV2hlbiBhIEthbGlpIGZhbWlseSZyc3F1bztzIHRheCBjb250cmFjdCB3YXMgdXAgdGhleSBoYWQgdG8gdHJhdmVsIHRvIHRoZSBjYXBpdGFsIHRvIGhhZ2dsZSB3aXRoIGdvdmVybm1lbnQgb2ZmaWNhbHMgYW5kIGhhbW1lciBvdXQgYSBuZXcgZGVhbC4gVGhlIGNvbnRyYWN0IHdvdWxkIGhhdmUgYSBzdGFydCBkYXRlLCBhbiBlbmQgZGF0ZSAoZm9yIGJvb2trZWVwaW5nIHB1cnBvc2VzIHRoZSBlbmQgZGF5IHdhcyBhbHdheXMgdGhlIDE1dGggb2YgdGhlIGVuZCBtb250aCksIGFuZCBhIHRheCByYXRlLiBJdCB3YXMgYWxzbyB0cmFkaXRpb25hbCBmb3IgYSBLYWxpaSBmYW1pbHkgdG8gZW5qb3kgYSBzaG9ydCB0aW1lIHBlcmlvZCBvZiB0YXggZnJlZSBsaXZpbmcgYmV0d2VlbiB0aGUgZW5kIG9mIHRoZWlyIGxhc3QgY29udHJhY3QgYW5kIHRoZSBzdGFydCBvZiB0aGUgbmV3IG9uZS4gVGhpcyB0aW1lIHBlcmlvZCB3YXMgYSBwb2ludCB0byBoYWdnbGUgb3ZlciBhcyB3ZWxsLjxcL3A+XHJcblxyXG48cD5UaGUgbGFuZCBvZiBLYWxpaSB3YXMgcHJvc3Blcm91cyBhbmQgdmVyeSBwb3B1bG91cyBhbmQsIGFzIGEgY29uc2VxdWVuY2UsIGdvdmVybm1lbnQgb2ZmaWNpYWxzIHdlcmUgb2Z0ZW4gb3ZlcndoZWxtZWQgd2l0aCB3b3JrLiBXaGVuIGEgZGVhbCB3YXMgYWdyZWVkIHVwb24gd2l0aCBhIGZhbWlseSwgdGhlIG9mZmljaWFscyB3b3VsZCBxdWlja2x5IHdyaXRlIGl0IGRvd24gaW4gc2hvcnRoYW5kIGFuZCBzZW5kIGl0IG9mZiB0byBiZSBwcm9jZXNzZWQuIFRoZXNlIHNjcmliYmxlZCBub3RlcyBoYWQgdG8gYmUgY29udmVydGVkIHRvIFhNTCBmb3JtYXQgdG8gYmUgZW50ZXJlZCBpbnRvIHRoZWlyIGNvbXB1dGVyIHN5c3RlbS4gU29tZXRpbWVzIHRoZSBzY3JpYmJsZSB3YXMgaW5jb25jbHVzaXZlIGFuZCB0aGUgZmFtaWx5IHdvdWxkIGhhdmUgdG8gYmUgcmVjYWxsZWQgdG8gdGhlIGNhcGl0YWwgZm9yIGFub3RoZXIgcm91bmQgb2YgaGFnZ2xpbmcuIFRoaXMgZW50aXJlIHByb2Nlc3Mgd2FzIHZlcnkgaW5lZmZpY2llbnQgYnV0IGl0IHdhcyB0aGUgd2F5IHRoZSBwZW9wbGUgb2YgS2FsaWkgaGFkIGFsd2F5cyBkb25lIGl0IGFuZCB0aGV5IHdlcmUgbm90IGFib3V0IHRvIGNoYW5nZSBhbnl0aW1lIHNvb24uPFwvcD5cclxuXHJcbjxwPllvdXIgam9iIGlzIHRvIGNvbnZlcnQgdGhlIHNjcmliYmxpbmdzIG9mIHRoZSBvZmZpY2lhbHMgaW50byBYTUwgZm9ybWF0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgZGF0YXNldHMsIG9uZSBwZXIgbGluZS4gRWFjaCBjb3JyZWN0IGxpbmUgY29udGFpbnMgdGhyZWUgcGllY2VzIG9mIGluZm9ybWF0aW9uOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRheCByYXRlXHJcblx0PHVsPlxyXG5cdFx0PGxpPkEgdGF4IHJhdGUgYWx3YXlzIGhhcyBhICZsc3F1bzslJnJzcXVvOyBhZnRlciBpdCBpZiBpdCBpcyBhIHdob2xlIG51bWJlciAoaS5lLiA1JSkuPFwvbGk+XHJcblx0XHQ8bGk+QSB0YXggcmF0ZSBuZXZlciBoYXMgYSBkZWNpbWFsIHBvaW50IGluIGl0LjxcL2xpPlxyXG5cdFx0PGxpPkEgdGF4IHJhdGUgbWF5IGNvbnRhaW4gYSBmcmFjdGlvbiBidXQgaXRzIGRlbm9taW5hdG9yIG11c3Qgb25seSBiZSBhIDIsIDQsIG9yIDguPFwvbGk+XHJcblx0XHQ8bGk+QSB0YXggcmF0ZSBtdXN0IGhhdmUgYSBudW1lcmF0b3IgdGhhdCBpcyBsZXNzIHRoYW4gaXRzIGRlbm9taW5hdG9yLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5Db250cmFjdCBFbmQgRGF0ZVxyXG5cdDx1bD5cclxuXHRcdDxsaT5BIGNvbnRyYWN0IGVuZCBkYXRlIGlzIGEgbnVtZXJpY2FsIHJlcHJlc2VudGF0aW9uIG9mIHRoZSBtb250aCAob25lIG9yIHR3byBkaWdpdHMpIGFuZCB0aGUgbGFzdCB0d28gZGlnaXRzIG9mIHRoZSB5ZWFyLiBUaGUgbW9udGggYW5kIHllYXIgbWF5IGJlIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBoeXBoZW4gKGkuZS4gMTItMDUgb3IgMTIwNSB3b3VsZCByZWZlciB0byAxNURFQzA1KS48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+Q29udHJhY3QgU3RhcnQgRGF0ZVxyXG5cdDx1bD5cclxuXHRcdDxsaT5BIGNvbnRyYWN0IHN0YXJ0IGRhdGUgaXMgYSBudW1lcmljYWwgcmVwcmVzZW50YXRpb24gb2YgdGhlIG1vbnRoIChvbmUgb3IgdHdvIGRpZ2l0cykgYW5kIGEgdHdvLWRpZ2l0IGRheSBvZiB0aGUgbW9udGguIFRoZSBtb250aCBhbmQgZGF5IG1heSBiZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgaHlwaGVuIChpLmUuIDEyLTA1IG9yIDEyMDUgd291bGQgcmVmZXIgdG8gMDVERUMwMykuPFwvbGk+XHJcblx0XHQ8bGk+QSBjb250cmFjdCBzdGFydCBkYXRlIG11c3Qgc3RhcnQgb24gb3IgYWZ0ZXIgdGhlIGN1cnJlbnQgZGF0ZS4gRm9yIGV4YW1wbGUsIHRoZSBjdXJyZW50IHllYXIgaXMgMjAwMy4gSWYgdGhlIHN0YXJ0IGRhdGUgaXMgMzA1IGl0IGlzIGFzc3VtZWQgdGhhdCB0aGUgeWVhciB0aGUgY29udHJhY3Qgc3RhcnRzIHdpbGwgYmUgMjAwNC5cclxuXHRcdDx1bD5cclxuXHRcdDxcL3VsPlxyXG5cdFx0PFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+Tm90ZTogVGhlcmUgbWF5IGJlIDAgb3IgbW9yZSBzcGFjZXMgYmV0d2VlbiBlYWNoIG9mIHRoZSB0aHJlZSBmaWVsZHMuPGJyIFwvPlxyXG5Ob3RlOiBUaGUgS2FsaWkgY2FsZW5kYXIgY29uc2lzdHMgb2YgdGhlIHR3ZWx2ZSBtb250aHMgZmFtaWxpYXIgdG8geW91LCBidXQgYWxsIG1vbnRocyBoYXZlIDMxIGRheXMuPGJyIFwvPlxyXG5Ob3RlOiBUaGUgbWF4aW11bSB0YXggcmF0ZSBpcyA5OS44NzUlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIHByaW50IHRoZSBjb3JyZWN0bHkgaW5kZW50ZWQgWE1MICg0IHNwYWNlcyBwZXIgaW5kZW50IGxldmVsKTo8XC9wPlxyXG5cclxuPHByZT5cclxuJmx0O0thbGlpIEluZGV4PU4mZ3Q7XHJcbiZuYnNwOyAmbmJzcDsgJmx0O3N0YXJ0ZGF0ZSZndDsoc3RhcnQgZGF0ZSkmbHQ7XC9zdGFydGRhdGUmZ3Q7XHJcbiZuYnNwOyAmbmJzcDsgJmx0O3JhdGUmZ3Q7KHRheCByYXRlKSZsdDtcL3JhdGUmZ3Q7XHJcbiZuYnNwOyAmbmJzcDsgJmx0O2VuZGRhdGUmZ3Q7KGVuZCBkYXRlKSZsdDtcL2VuZGRhdGUmZ3Q7XHJcbiZsdDtcL0thbGlpJmd0OzxcL3ByZT5cclxuXHJcbjxwPk4gc2hvdWxkIGJlIHJlcGxhY2VkIGJ5IHRoZSBkYXRhIHNldCBudW1iZXIsIChzdGFydCBkYXRlKSBieSB0aGUgc3RhcnQgZGF0ZSwgKHRheCByYXRlKSBieSB0aGUgdGF4IHJhdGUsIGFuZCAoZW5kIGRhdGUpIGJ5IHRoZSBlbmQgZGF0ZS4gSWYgbm8gb3V0cHV0IGNvdWxkIGJlIGNvbXB1dGVkIGJlY2F1c2Ugb2YgZWl0aGVyIGJhZCBvciBhbWJpZ3VvdXMgZGF0YSwgc2ltcGx5IHByaW50ICZsdDtLYWxpaSBJbmRleD1OICZndDtCQUQgSU5QVVQmbHQ7XC9LYWxpaSZndDssIHdoZXJlIE4gc2hvdWxkIGJlIHJlcGxhY2VkIGJ5IHRoZSBkYXRhIHNldCBudW1iZXIuPFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSBmb3JtYXQgZm9yIHRoZSBzdGFydCBkYXRlIGlzIERETU1NWVkuIFRoZSBmb3JtYXQgZm9yIHRoZSBlbmQgZGF0ZSBpcyAxNU1NTVlZLiBXaGVyZSBERCBpcyB0aGUgemVyby1wYWRkZWQgZGF5IG9mIG1vbnRoICgwMS0zMSksIE1NTSBpcyB0aGUgbW9udGggaW4gdXBwZXItY2FzZSBsZXR0ZXJzIChKQU4sIEZFQiwgTUFSLCBBUFIsIE1BWSwgSlVOLCBKVUwsIEFVRywgU0VQLCBPQ1QsIE5PViwgREVDKSwgYW5kIFlZIGlzIHRoZSB6ZXJvLXBhZGRlZCBsYXN0IDIgZGlnaXRzIG9mIHRoZSB5ZWFyICgwMC05OSkuPFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSB0YXggcmF0ZSBzaG91bGQgYmUgYWNjdXJhdGUgdG8gMyBkZWNpbWFsIHBsYWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2003 Greater New York Programming Contest D번