시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 98 12 9 10.588%

문제

요즘 한국에는 스타트업 열풍이 불고 있다. 상근이는 스타트업에게 사무실을 빌려주는 스타트업을 시작했다. 사무실은 총 N개가 있다. 가장 왼쪽에 있는 사무실은 1번, 가장 오른쪽은 N번이며, 그 사이 사무실은 순서대로 번호가 매겨져 있다. 

처음에 사무실은 모두 비어있다. 사무실에 회사가 입주할 때, 회사는 상근이에게 다음과 같은 네 가지 정보를 알려주어야 한다.

  • T: 입주일 (상근이가 스타트업을 시작한 날이 1일이다)
  • K: 사무실 번호
  • Z: 하루 수익 (회사가 손해를 보고있다면 음수일 수도 있다)
  • S: 입주일 당시에 그 회사가 가지고 있는 금액

만약 입주하려고 하는 사무실 K에 이미 회사가 있다면, K에 있던 회사는 짐을 싸서 사무실을 비워야 한다. 또, 입주하는 날은 하루종일 이사를 해야 하기 때문에, 일을 하지 않아서 수익을 올리지 않는다.

놀랍게도 이 사무실에 입주한 회사는 매일 매일 Z만큼 수익을 올리며, 이 금액은 늘어나지도, 줄어들지도 않는다.

가끔 상근이는 가장 부유한 회사가 어디인지 알아본다. 항상 연속으로 붙어있는 사무실을 조사하며, 다음과 같이 나타낼 수 있다.

  • T: 조사하는 날 (상근이가 스타트업을 시작한 날이 1일)
  • A와 B: A번 사무실부터 B번까지 조사

상근이는 항상 입주한 회사의 모든 업무가 끝난 다음에 조사를 한다. (사무실에서 밤 8시가 넘었는데 일을 할 수 없다) 따라서, 각 회사가 하루에 버는 수익은 항상 입주할 때 보고한 금액이다.

이벤트의 정보가 주어졌을 때, 조사에 대한 답을 구하는 프로그램을 작성하시오. 회사가 입주하는 정보와 상근이가 조사하는 정보를 합쳐서 이벤트라고 한다.

입력

첫째 줄에 사무실의 개수 N과 이벤트의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

다음 M개 줄에는 이벤트의 정보가 주어진다. 회사의 입주는 "1 T K Z S"와 같이 주어지며, 상근이의 조사는 "2 T A B"로 주어진다.

모든 이벤트는 일어난 순서대로 주어진며, 하루에 일어나는 이벤트는 최대 한 개 이다. 따라서, T가 항상 증가하는 순서로 주어진다. 마지막 이벤트가 일어난 날은 106보다 작으며, Z와 S의 절댓값도 106보다 작다.

출력

상근이의 질문에 대한 답(주어진 구간에 포함 되는 가장 부유한 회사가 가지고 있는 금액)을 한 줄에 하나씩 출력한다. 만약, 그 구간에 있는 회사가 하나도 없다면, "nema"를 출력한다.

예제 입력 1

2 4
1 1 1 2 4
1 2 2 3 2
2 5 1 2
2 7 1 2

예제 출력 1

12
17
W3sicHJvYmxlbV9pZCI6IjI3ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWQwYzBcdWQyYjhcdWM1YzUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzY5NFx1Yzk5OCBcdWQ1NWNcdWFkNmRcdWM1ZDBcdWIyOTQgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1IFx1YzVmNFx1ZDQ4ZFx1Yzc3NCBcdWJkODhcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNWQwXHVhYzhjIFx1YzBhY1x1YmIzNFx1YzJlNFx1Yzc0NCBcdWJlNGNcdWI4MjRcdWM4ZmNcdWIyOTQgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC4gXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQwIFx1Y2QxZCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQwIDFcdWJjODgsIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgTlx1YmM4OFx1Yzc3NFx1YmE3MCwgXHVhZGY4IFx1YzBhY1x1Yzc3NCBcdWMwYWNcdWJiMzRcdWMyZTRcdWM3NDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWNjOThcdWM3NGNcdWM1ZDAgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzBhY1x1YmIzNFx1YzJlNFx1YzVkMCBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjNzg1XHVjOGZjXHVkNTYwIFx1YjU0YywgXHVkNjhjXHVjMGFjXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjEyNCBcdWFjMDBcdWM5YzAgXHVjODE1XHViY2Y0XHViOTdjIFx1YzU0Y1x1YjgyNFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VDogXHVjNzg1XHVjOGZjXHVjNzdjIChcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWIwYTBcdWM3NzQgMVx1Yzc3Y1x1Yzc3NFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+SzogXHVjMGFjXHViYjM0XHVjMmU0IFx1YmM4OFx1ZDYzODxcL2xpPlxyXG5cdDxsaT5aOiBcdWQ1NThcdWI4ZTggXHVjMjE4XHVjNzc1IChcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjMTkwXHVkNTc0XHViOTdjIFx1YmNmNFx1YWNlMFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWM3NGNcdWMyMThcdWM3N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+UzogXHVjNzg1XHVjOGZjXHVjNzdjIFx1YjJmOVx1YzJkY1x1YzVkMCBcdWFkZjggXHVkNjhjXHVjMGFjXHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVhZTA4XHVjNTYxPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1Yzc4NVx1YzhmY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVjMGFjXHViYjM0XHVjMmU0IEtcdWM1ZDAgXHVjNzc0XHViYmY4IFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQsIEtcdWM1ZDAgXHVjNzg4XHViMzU4IFx1ZDY4Y1x1YzBhY1x1YjI5NCBcdWM5ZDBcdWM3NDQgXHVjMmY4XHVjMTFjIFx1YzBhY1x1YmIzNFx1YzJlNFx1Yzc0NCZuYnNwO1x1YmU0NFx1YzZjY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjNzg1XHVjOGZjXHVkNTU4XHViMjk0IFx1YjBhMFx1Yzc0MCBcdWQ1NThcdWI4ZThcdWM4ODVcdWM3N2MgXHVjNzc0XHVjMGFjXHViOTdjIFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzExYyBcdWMyMThcdWM3NzVcdWM3NDQgXHVjNjJjXHViOWFjXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTgwXHViNzhkXHVhYzhjXHViM2M0IFx1Yzc3NCBcdWMwYWNcdWJiMzRcdWMyZTRcdWM1ZDAgXHVjNzg1XHVjOGZjXHVkNTVjIFx1ZDY4Y1x1YzBhY1x1YjI5NCBcdWI5ZTRcdWM3N2MgXHViOWU0XHVjNzdjIFpcdWI5Y2NcdWQwN2MgXHVjMjE4XHVjNzc1XHVjNzQ0IFx1YzYyY1x1YjlhY1x1YmE3MCwgXHVjNzc0IFx1YWUwOFx1YzU2MVx1Yzc0MCBcdWIyOThcdWM1YjRcdWIwOThcdWM5YzBcdWIzYzQsIFx1YzkwNFx1YzViNFx1YjRlNFx1YzljMFx1YjNjNCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YjA1NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YmQ4MFx1YzcyMFx1ZDU1YyBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjNWI0XHViNTE0XHVjNzc4XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YmNmOFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQ0IFx1Yzg3MFx1YzBhY1x1ZDU1OFx1YmE3MCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UOiBcdWM4NzBcdWMwYWNcdWQ1NThcdWIyOTQgXHViMGEwIChcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWIwYTBcdWM3NzQgMVx1Yzc3Yyk8XC9saT5cclxuXHQ8bGk+QVx1YzY0MCBCOiBBXHViYzg4IFx1YzBhY1x1YmIzNFx1YzJlNFx1YmQ4MFx1ZDEzMCBCXHViYzg4XHVhZTRjXHVjOWMwIFx1Yzg3MFx1YzBhYzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNzg1XHVjOGZjXHVkNTVjIFx1ZDY4Y1x1YzBhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNWM1XHViYjM0XHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjODcwXHVjMGFjXHViOTdjIFx1ZDU1Y1x1YjJlNC4gKFx1YzBhY1x1YmIzNFx1YzJlNFx1YzVkMFx1YzExYyBcdWJjMjQgOFx1YzJkY1x1YWMwMCBcdWIxMThcdWM1YzhcdWIyOTRcdWIzNzAgXHVjNzdjXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0KSBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWMwMSBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVkNTU4XHViOGU4XHVjNWQwIFx1YmM4NFx1YjI5NCBcdWMyMThcdWM3NzVcdWM3NDAgXHVkNTZkXHVjMGMxIFx1Yzc4NVx1YzhmY1x1ZDU2MCBcdWI1NGMgXHViY2Y0XHVhY2UwXHVkNTVjIFx1YWUwOFx1YzU2MVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViY2E0XHVkMmI4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4NzBcdWMwYWNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVkNjhjXHVjMGFjXHVhYzAwIFx1Yzc4NVx1YzhmY1x1ZDU1OFx1YjI5NCBcdWM4MTVcdWJjZjRcdWM2NDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzg3MFx1YzBhY1x1ZDU1OFx1YjI5NCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVkNTY5XHVjY2QwXHVjMTFjJm5ic3A7XHVjNzc0XHViY2E0XHVkMmI4XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1Yzc3NFx1YmNhNFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBNICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3NFx1YmNhNFx1ZDJiOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ2OGNcdWMwYWNcdWM3NTggXHVjNzg1XHVjOGZjXHViMjk0ICZxdW90OzEgVCBLIFogUyZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjODcwXHVjMGFjXHViMjk0ICZxdW90OzIgVCBBIEImcXVvdDtcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjNzc0XHViY2E0XHVkMmI4XHViMjk0IFx1Yzc3Y1x1YzViNFx1YjA5YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViYTcwLCBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVjNzdjXHVjNWI0XHViMDk4XHViMjk0IFx1Yzc3NFx1YmNhNFx1ZDJiOFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgVFx1YWMwMCBcdWQ1NmRcdWMwYzEgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM3NzRcdWJjYTRcdWQyYjhcdWFjMDAgXHVjNzdjXHVjNWI0XHViMDljIFx1YjBhMFx1Yzc0MCAxMDxzdXA+NjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzNjXHViYTcwLCBaXHVjNjQwIFNcdWM3NTggXHVjODA4XHViMzEzXHVhYzEyXHViM2M0IDEwPHN1cD42PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzljOFx1YmIzOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmY1KFx1YzhmY1x1YzViNFx1YzljNCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4IFx1YjQxOFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViZDgwXHVjNzIwXHVkNTVjIFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWUwOFx1YzU2MSlcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWRmOCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWQ1NThcdWIwOThcdWIzYzQgXHVjNWM2XHViMmU0XHViYTc0LCAmcXVvdDtuZW1hJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJTlNQRUtUT1IiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbmV3IHRvd24gd2FzIGp1c3QgaW5hdWd1cmF0ZWQgaW4gYSBzbWFsbCBjb3VudHJ5LiBBcyB1c3VhbCwgTWlya28gaGFzIHNlY3VyZWQgdGhlIHBvc2l0aW9uIG9mIHRoZSBjaGllZiB0YXggaW5zcGVjdG9yLiBIaXMgZHV0eSBpcyBlbnN1cmluZyBhZGVxdWF0ZSBhY2NvdW50aW5nIGluIGFsbCB0aGUgZGlmZmVyZW50IGNvbXBhbmllcyBpbiB0aGUgdG93bi48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIE4gYnVzaW5lc3Mgb2ZmaWNlcyBhbG9uZyB0aGUgbWFpbiBzdHJlZXQsIG51bWJlcmVkIDEgdG8gTiBmcm9tIGxlZnQgdG8gcmlnaHQuIEFsbCBvZmZpY2VzIGFyZSBlbXB0eSBpbiB0aGUgYmVnaW5uaW5nOyBpbiB0aW1lLCBjb21wYW5pZXMgd2lsbCBtb3ZlIGluIGFuZCBvdXQgb2YgdGhlc2Ugb2ZmaWNlcy4gRnJvbSB0aW1lIHRvIHRpbWUsIE1pcmtvIHdpbGwgcGFzcyBieSBzb21lIG9mIHRoZSBvZmZpY2VzIGFuZCBpbnNwZWN0IHRoZSBhY2NvdW50aW5nIG9mIG9ubHkgb25lIGNvbXBhbnksIHRoZSBjdXJyZW50bHkgd2VhbHRoaWVzdCBvbmUgaW4gdGhvc2Ugb2ZmaWNlcy48XC9wPlxyXG5cclxuPHA+QSBjb21wYW55IG1vdmluZyBpbiBpcyBkZXNjcmliZWQgYnkgZm91ciBpbnRlZ2Vyczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UICZuZGFzaDsgdGhlIG1vdmUtaW4gZGF5LCBudW1iZXJlZCBmcm9tIHRvd24gaW5hdWd1cmF0aW9uICh3aGljaCBpcyBkYXkgMSksPFwvbGk+XHJcblx0PGxpPksgJm5kYXNoOyB0aGUgb2ZmaWNlIG51bWJlciw8XC9saT5cclxuXHQ8bGk+WiAmbmRhc2g7IHRoZSBkYWlseSBwcm9maXQgb2YgdGhlIGNvbXBhbnkgKGNhbiBiZSBuZWdhdGl2ZSBpZiB0aGUgY29tcGFueSBpcyBsb3NpbmcgbW9uZXkpLDxcL2xpPlxyXG5cdDxsaT5TICZuZGFzaDsgYmFsYW5jZSBvZiB0aGUgY29tcGFueSYjMzk7cyBhY2NvdW50IG9uIG1vdmUtaW4gZGF5LiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIGFscmVhZHkgYSBjb21wYW55IGluIG9mZmljZSBLLCB0aGF0IGNvbXBhbnkgbW92ZXMgb3V0IHdoZW4gdGhlIG5ldyBjb21wYW55IG1vdmVzIGluLiBUaGUgbmV3IGNvbXBhbnkgZG9lc24mIzM5O3Qgb3BlbiBmb3IgYnVzaW5lc3MgKG9yIGVhcm4gcHJvZml0KSB1bnRpbCB0aGUgZGF5IGFmdGVyIG1vdmUtaW4uPFwvcD5cclxuXHJcbjxwPk1pcmtvJiMzOTtzIGluc3BlY3Rpb24gc3Ryb2xsIGlzIGRlc2NyaWJlZCBieSB0aHJlZSBpbnRlZ2Vyczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UICZuZGFzaDsgdGhlIGluc3BlY3Rpb24gZGF5LCBudW1iZXJlZCBmcm9tIHRvd24gaW5hdWd1cmF0aW9uLDxcL2xpPlxyXG5cdDxsaT5BIGFuZCBCICZuZGFzaDsgTWlya28gd2lsbCBwYXNzIGJ5IGFsbCBvZmZpY2VzIHdpdGggbnVtYmVycyBiZXR3ZWVuIEEgYW5kIEIsIGluY2x1c2l2ZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5TaW5jZSBNaXJrbyB3b3JrcyBvbmx5IGF0IHRoZSBlbmQgb2YgdGhlIGRheSwgYWxsIGNvbXBhbmllcyB3aWxsIGhhdmUgYWxyZWFkeSBmaW5pc2hlZCBidXNpbmVzcyBhbmQgcG9zdGVkIHByb2ZpdCBmb3IgdGhlIGRheSBieSB0aGUgdGltZSBvZiBNaXJrbyYjMzk7cyBzdHJvbGwuPFwvcD5cclxuXHJcbjxwPkhlbHAgTWlya28gYnkgd3JpdGluZyBhIHByb2dyYW0gdG8gZmluZCwgZm9yIGVhY2ggc3Ryb2xsLCB0aGUgYWNjb3VudCBiYWxhbmNlIG9mIHRoZSBjdXJyZW50bHkgd2VhbHRoaWVzdCBjb21wYW55IHRoYXQgTWlya28gaXMgcGFzc2luZyBieS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSBhbmQgTSAoMSAmbGU7IE0gJmxlOyAzMDAgMDAwKSwgdGhlIG51bWJlciBvZiBvZmZpY2VzIGFuZCBldmVudHMsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gbGluZXMgY29udGFpbnMgYSBkZXNjcmlwdGlvbiBvZiBvbmUgZXZlbnQsIGZvcm1hdHRlZCBlaXRoZXIgYXMgJmxkcXVvOzEgVCBLIFogUyZyZHF1bzsgKGZvciBjb21wYW55IG1vdmUtaW4pIG9yIGFzICZsZHF1bzsyIFQgQSBCJnJkcXVvOyAoZm9yIE1pcmtvJiMzOTtzIGluc3BlY3Rpb24gc3Ryb2xsKS48XC9wPlxyXG5cclxuPHA+QWxsIGV2ZW50cyBhcmUgZ2l2ZW4gY2hyb25vbG9naWNhbGx5LCBhbmQgYXQgbW9zdCBvbmUgZXZlbnQgd2lsbCBoYXBwZW4gZWFjaCBkYXkgKHRoYXQgaXMsIFQgd2lsbCBiZSBzdHJpY3RseSBpbmNyZWFzaW5nKS4gVGhlIGxhc3QgZXZlbnQmIzM5O3MgZGF5IG51bWJlciB3aWxsIGJlIGxlc3MgdGhhbiAxMDxzdXA+NjxcL3N1cD4sIGFuZCBhbGwgWiBhbmQgUyBudW1iZXJzJiMzOTsgYWJzb2x1dGUgdmFsdWVzIHdpbGwgYmUgbGVzcyB0aGFuIDEwPHN1cD42PFwvc3VwPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBNaXJrbyYjMzk7cyBzdHJvbGwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIHRoZSBhY2NvdW50IGJhbGFuY2Ugb2YgdGhlIGNvbXBhbnkgdGhhdCBNaXJrbyB3aWxsIGluc3BlY3QsIG9yIHRoZSB3b3JkICZsZHF1bztuZW1hJnJkcXVvOyAod2l0aG91dCBxdW90ZXMpIGlmIGFsbCBvZmZpY2VzIHRoYXQgaGUgd2lsbCBwYXNzIGJ5IGFyZSBlbXB0eS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #2 6번