시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB202231712.782%

문제

요즘 한국에는 스타트업 열풍이 불고 있다. 상근이는 스타트업에게 사무실을 빌려주는 스타트업을 시작했다. 사무실은 총 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

예제 입력 2

3 6
1 1 1 4 -2
1 2 2 2 6
2 3 3 1
2 4 3 1
1 5 3 -6 20
2 6 2 3

예제 출력 2

8
10
14

예제 입력 3

5 9
1 1 5 4 -5
2 2 3 5
1 3 4 6 9
2 4 1 2
1 6 2 2 3
2 8 2 1
1 9 4 0 17
2 10 5 5
2 11 1 4

예제 출력 3

-1
nema
7
31
17
W3sicHJvYmxlbV9pZCI6IjI3ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWQwYzBcdWQyYjhcdWM1YzUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzY5NFx1Yzk5OCBcdWQ1NWNcdWFkNmRcdWM1ZDBcdWIyOTQgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1IFx1YzVmNFx1ZDQ4ZFx1Yzc3NCBcdWJkODhcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNWQwXHVhYzhjIFx1YzBhY1x1YmIzNFx1YzJlNFx1Yzc0NCBcdWJlNGNcdWI4MjRcdWM4ZmNcdWIyOTQgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC4gXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQwIFx1Y2QxZCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQwIDFcdWJjODgsIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDAgTlx1YmM4OFx1Yzc3NFx1YmE3MCwgXHVhZGY4IFx1YzBhY1x1Yzc3NCBcdWMwYWNcdWJiMzRcdWMyZTRcdWM3NDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWNjOThcdWM3NGNcdWM1ZDAgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YzBhY1x1YmIzNFx1YzJlNFx1YzVkMCBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjNzg1XHVjOGZjXHVkNTYwIFx1YjU0YywgXHVkNjhjXHVjMGFjXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjEyNCBcdWFjMDBcdWM5YzAgXHVjODE1XHViY2Y0XHViOTdjIFx1YzU0Y1x1YjgyNFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VDogXHVjNzg1XHVjOGZjXHVjNzdjIChcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWIwYTBcdWM3NzQgMVx1Yzc3Y1x1Yzc3NFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+SzogXHVjMGFjXHViYjM0XHVjMmU0IFx1YmM4OFx1ZDYzODxcL2xpPlxyXG5cdDxsaT5aOiBcdWQ1NThcdWI4ZTggXHVjMjE4XHVjNzc1IChcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjMTkwXHVkNTc0XHViOTdjIFx1YmNmNFx1YWNlMFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWM3NGNcdWMyMThcdWM3N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+UzogXHVjNzg1XHVjOGZjXHVjNzdjIFx1YjJmOVx1YzJkY1x1YzVkMCBcdWFkZjggXHVkNjhjXHVjMGFjXHVhYzAwIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVhZTA4XHVjNTYxPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1Yzc4NVx1YzhmY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHVjMGFjXHViYjM0XHVjMmU0IEtcdWM1ZDAgXHVjNzc0XHViYmY4IFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQsIEtcdWM1ZDAgXHVjNzg4XHViMzU4IFx1ZDY4Y1x1YzBhY1x1YjI5NCBcdWM5ZDBcdWM3NDQgXHVjMmY4XHVjMTFjIFx1YzBhY1x1YmIzNFx1YzJlNFx1Yzc0NCZuYnNwO1x1YmU0NFx1YzZjY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjNzg1XHVjOGZjXHVkNTU4XHViMjk0IFx1YjBhMFx1Yzc0MCBcdWQ1NThcdWI4ZThcdWM4ODVcdWM3N2MgXHVjNzc0XHVjMGFjXHViOTdjIFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzExYyBcdWMyMThcdWM3NzVcdWM3NDQgXHVjNjJjXHViOWFjXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTgwXHViNzhkXHVhYzhjXHViM2M0IFx1Yzc3NCBcdWMwYWNcdWJiMzRcdWMyZTRcdWM1ZDAgXHVjNzg1XHVjOGZjXHVkNTVjIFx1ZDY4Y1x1YzBhY1x1YjI5NCBcdWI5ZTRcdWM3N2MgXHViOWU0XHVjNzdjIFpcdWI5Y2NcdWQwN2MgXHVjMjE4XHVjNzc1XHVjNzQ0IFx1YzYyY1x1YjlhY1x1YmE3MCwgXHVjNzc0IFx1YWUwOFx1YzU2MVx1Yzc0MCBcdWIyOThcdWM1YjRcdWIwOThcdWM5YzBcdWIzYzQsIFx1YzkwNFx1YzViNFx1YjRlNFx1YzljMFx1YjNjNCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YjA1NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YmQ4MFx1YzcyMFx1ZDU1YyBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjNWI0XHViNTE0XHVjNzc4XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YmNmOFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzQ0IFx1Yzg3MFx1YzBhY1x1ZDU1OFx1YmE3MCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UOiBcdWM4NzBcdWMwYWNcdWQ1NThcdWIyOTQgXHViMGEwIChcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMmE0XHVkMGMwXHVkMmI4XHVjNWM1XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWIwYTBcdWM3NzQgMVx1Yzc3Yyk8XC9saT5cclxuXHQ8bGk+QVx1YzY0MCBCOiBBXHViYzg4IFx1YzBhY1x1YmIzNFx1YzJlNFx1YmQ4MFx1ZDEzMCBCXHViYzg4XHVhZTRjXHVjOWMwIFx1Yzg3MFx1YzBhYzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNzg1XHVjOGZjXHVkNTVjIFx1ZDY4Y1x1YzBhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNWM1XHViYjM0XHVhYzAwIFx1YjA1ZFx1YjA5YyBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjODcwXHVjMGFjXHViOTdjIFx1ZDU1Y1x1YjJlNC4gKFx1YzBhY1x1YmIzNFx1YzJlNFx1YzVkMFx1YzExYyBcdWJjMjQgOFx1YzJkY1x1YWMwMCBcdWIxMThcdWM1YzhcdWIyOTRcdWIzNzAgXHVjNzdjXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0KSBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWMwMSBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVkNTU4XHViOGU4XHVjNWQwIFx1YmM4NFx1YjI5NCBcdWMyMThcdWM3NzVcdWM3NDAgXHVkNTZkXHVjMGMxIFx1Yzc4NVx1YzhmY1x1ZDU2MCBcdWI1NGMgXHViY2Y0XHVhY2UwXHVkNTVjIFx1YWUwOFx1YzU2MVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViY2E0XHVkMmI4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4NzBcdWMwYWNcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVkNjhjXHVjMGFjXHVhYzAwIFx1Yzc4NVx1YzhmY1x1ZDU1OFx1YjI5NCBcdWM4MTVcdWJjZjRcdWM2NDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzg3MFx1YzBhY1x1ZDU1OFx1YjI5NCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVkNTY5XHVjY2QwXHVjMTFjJm5ic3A7XHVjNzc0XHViY2E0XHVkMmI4XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGFjXHViYjM0XHVjMmU0XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVhY2ZjIFx1Yzc3NFx1YmNhNFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBNICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3NFx1YmNhNFx1ZDJiOFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ2OGNcdWMwYWNcdWM3NTggXHVjNzg1XHVjOGZjXHViMjk0ICZxdW90OzEgVCBLIFogUyZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjODcwXHVjMGFjXHViMjk0ICZxdW90OzIgVCBBIEImcXVvdDtcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjNzc0XHViY2E0XHVkMmI4XHViMjk0IFx1Yzc3Y1x1YzViNFx1YjA5YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViYTcwLCBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVjNzdjXHVjNWI0XHViMDk4XHViMjk0IFx1Yzc3NFx1YmNhNFx1ZDJiOFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxYyBcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgVFx1YWMwMCBcdWQ1NmRcdWMwYzEgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOSBcdWM3NzRcdWJjYTRcdWQyYjhcdWFjMDAgXHVjNzdjXHVjNWI0XHViMDljIFx1YjBhMFx1Yzc0MCAxMDxzdXA+NjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzNjXHViYTcwLCBaXHVjNjQwIFNcdWM3NTggXHVjODA4XHViMzEzXHVhYzEyXHViM2M0IDEwPHN1cD42PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzljOFx1YmIzOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmY1KFx1YzhmY1x1YzViNFx1YzljNCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4IFx1YjQxOFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViZDgwXHVjNzIwXHVkNTVjIFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWUwOFx1YzU2MSlcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWRmOCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDY4Y1x1YzBhY1x1YWMwMCBcdWQ1NThcdWIwOThcdWIzYzQgXHVjNWM2XHViMmU0XHViYTc0LCAmcXVvdDtuZW1hJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzg4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSU5TUEVLVE9SIiwiZGVzY3JpcHRpb24iOiI8cD5BIG5ldyB0b3duIHdhcyBqdXN0IGluYXVndXJhdGVkIGluIGEgc21hbGwgY291bnRyeS4gQXMgdXN1YWwsIE1pcmtvIGhhcyBzZWN1cmVkIHRoZSBwb3NpdGlvbiBvZiB0aGUgY2hpZWYgdGF4IGluc3BlY3Rvci4gSGlzIGR1dHkgaXMgZW5zdXJpbmcgYWRlcXVhdGUgYWNjb3VudGluZyBpbiBhbGwgdGhlIGRpZmZlcmVudCBjb21wYW5pZXMgaW4gdGhlIHRvd24uPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOIGJ1c2luZXNzIG9mZmljZXMgYWxvbmcgdGhlIG1haW4gc3RyZWV0LCBudW1iZXJlZCAxIHRvIE4gZnJvbSBsZWZ0IHRvIHJpZ2h0LiBBbGwgb2ZmaWNlcyBhcmUgZW1wdHkgaW4gdGhlIGJlZ2lubmluZzsgaW4gdGltZSwgY29tcGFuaWVzIHdpbGwgbW92ZSBpbiBhbmQgb3V0IG9mIHRoZXNlIG9mZmljZXMuIEZyb20gdGltZSB0byB0aW1lLCBNaXJrbyB3aWxsIHBhc3MgYnkgc29tZSBvZiB0aGUgb2ZmaWNlcyBhbmQgaW5zcGVjdCB0aGUgYWNjb3VudGluZyBvZiBvbmx5IG9uZSBjb21wYW55LCB0aGUgY3VycmVudGx5IHdlYWx0aGllc3Qgb25lIGluIHRob3NlIG9mZmljZXMuPFwvcD5cclxuXHJcbjxwPkEgY29tcGFueSBtb3ZpbmcgaW4gaXMgZGVzY3JpYmVkIGJ5IGZvdXIgaW50ZWdlcnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VCAmbmRhc2g7IHRoZSBtb3ZlLWluIGRheSwgbnVtYmVyZWQgZnJvbSB0b3duIGluYXVndXJhdGlvbiAod2hpY2ggaXMgZGF5IDEpLDxcL2xpPlxyXG5cdDxsaT5LICZuZGFzaDsgdGhlIG9mZmljZSBudW1iZXIsPFwvbGk+XHJcblx0PGxpPlogJm5kYXNoOyB0aGUgZGFpbHkgcHJvZml0IG9mIHRoZSBjb21wYW55IChjYW4gYmUgbmVnYXRpdmUgaWYgdGhlIGNvbXBhbnkgaXMgbG9zaW5nIG1vbmV5KSw8XC9saT5cclxuXHQ8bGk+UyAmbmRhc2g7IGJhbGFuY2Ugb2YgdGhlIGNvbXBhbnkmIzM5O3MgYWNjb3VudCBvbiBtb3ZlLWluIGRheS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBhbHJlYWR5IGEgY29tcGFueSBpbiBvZmZpY2UgSywgdGhhdCBjb21wYW55IG1vdmVzIG91dCB3aGVuIHRoZSBuZXcgY29tcGFueSBtb3ZlcyBpbi4gVGhlIG5ldyBjb21wYW55IGRvZXNuJiMzOTt0IG9wZW4gZm9yIGJ1c2luZXNzIChvciBlYXJuIHByb2ZpdCkgdW50aWwgdGhlIGRheSBhZnRlciBtb3ZlLWluLjxcL3A+XHJcblxyXG48cD5NaXJrbyYjMzk7cyBpbnNwZWN0aW9uIHN0cm9sbCBpcyBkZXNjcmliZWQgYnkgdGhyZWUgaW50ZWdlcnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VCAmbmRhc2g7IHRoZSBpbnNwZWN0aW9uIGRheSwgbnVtYmVyZWQgZnJvbSB0b3duIGluYXVndXJhdGlvbiw8XC9saT5cclxuXHQ8bGk+QSBhbmQgQiAmbmRhc2g7IE1pcmtvIHdpbGwgcGFzcyBieSBhbGwgb2ZmaWNlcyB3aXRoIG51bWJlcnMgYmV0d2VlbiBBIGFuZCBCLCBpbmNsdXNpdmUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+U2luY2UgTWlya28gd29ya3Mgb25seSBhdCB0aGUgZW5kIG9mIHRoZSBkYXksIGFsbCBjb21wYW5pZXMgd2lsbCBoYXZlIGFscmVhZHkgZmluaXNoZWQgYnVzaW5lc3MgYW5kIHBvc3RlZCBwcm9maXQgZm9yIHRoZSBkYXkgYnkgdGhlIHRpbWUgb2YgTWlya28mIzM5O3Mgc3Ryb2xsLjxcL3A+XHJcblxyXG48cD5IZWxwIE1pcmtvIGJ5IHdyaXRpbmcgYSBwcm9ncmFtIHRvIGZpbmQsIGZvciBlYWNoIHN0cm9sbCwgdGhlIGFjY291bnQgYmFsYW5jZSBvZiB0aGUgY3VycmVudGx5IHdlYWx0aGllc3QgY29tcGFueSB0aGF0IE1pcmtvIGlzIHBhc3NpbmcgYnkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMsIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCkgYW5kIE0gKDEgJmxlOyBNICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgb2Ygb2ZmaWNlcyBhbmQgZXZlbnRzLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIGEgZGVzY3JpcHRpb24gb2Ygb25lIGV2ZW50LCBmb3JtYXR0ZWQgZWl0aGVyIGFzICZsZHF1bzsxIFQgSyBaIFMmcmRxdW87IChmb3IgY29tcGFueSBtb3ZlLWluKSBvciBhcyAmbGRxdW87MiBUIEEgQiZyZHF1bzsgKGZvciBNaXJrbyYjMzk7cyBpbnNwZWN0aW9uIHN0cm9sbCkuPFwvcD5cclxuXHJcbjxwPkFsbCBldmVudHMgYXJlIGdpdmVuIGNocm9ub2xvZ2ljYWxseSwgYW5kIGF0IG1vc3Qgb25lIGV2ZW50IHdpbGwgaGFwcGVuIGVhY2ggZGF5ICh0aGF0IGlzLCBUIHdpbGwgYmUgc3RyaWN0bHkgaW5jcmVhc2luZykuIFRoZSBsYXN0IGV2ZW50JiMzOTtzIGRheSBudW1iZXIgd2lsbCBiZSBsZXNzIHRoYW4gMTA8c3VwPjY8XC9zdXA+LCBhbmQgYWxsIFogYW5kIFMgbnVtYmVycyYjMzk7IGFic29sdXRlIHZhbHVlcyB3aWxsIGJlIGxlc3MgdGhhbiAxMDxzdXA+NjxcL3N1cD4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggTWlya28mIzM5O3Mgc3Ryb2xsIG91dHB1dCBhIGxpbmUgY29udGFpbmluZyB0aGUgYWNjb3VudCBiYWxhbmNlIG9mIHRoZSBjb21wYW55IHRoYXQgTWlya28gd2lsbCBpbnNwZWN0LCBvciB0aGUgd29yZCAmbGRxdW87bmVtYSZyZHF1bzsgKHdpdGhvdXQgcXVvdGVzKSBpZiBhbGwgb2ZmaWNlcyB0aGF0IGhlIHdpbGwgcGFzcyBieSBhcmUgZW1wdHkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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