시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 256 71 62 31.959%

문제

전대프연(전국 대학생 프로그래밍 대회 동아리 연합)에서는 매년 프로그래밍 대회를 연다. 올해도 무사히 대회를 개최한 전대프연 회장 성진은 수고해준 스태프들에게 수고비를 주기로 하였다. 하지만 몇몇 스태프는 일을 열심히하지 않았기 때문에 성진은 일을 열심히 한 사람에게만 주기로했다. 하지만 일을 무진장 열심히 한 사람과 덜 열심히 한 사람에게 수고비를 똑같이 주는 것은 불공평하다.

고민을 한 성진은 수고비를 받을 사람을 선출하는 방식으로 ALPS(Allegro Leader Picking System) 을 사용하기로 결심했다. ALPS는 이름에서 보이듯이, 아주 유쾌하고 빠르게 사람들을 선별하는 방법이다. 

우선 대회 참가자들은  "수고비를 받을 가치가 있는 스태프" 한명을 선택해 투표를 한다. (참가자가 투표를 하지 않을 수도 있다.) 이 투표결과, 전체 대회 참가자의 5% 미만의 득표를 얻은 사람은 열심히 일을 하지 않은 스태프이므로 후보에서 제외해버린다. 이제 남은 스태프마다, 받은 득표수를 1로 나눈 값, 2로 나눈 값... 14로 나눈 값을 구한다. 이렇게 구한 14개의 실수가 그 스태프의 '점수'들이 된다.

이렇게 14 * (후보 스태프의 명수) 개의 실수를 가진 점수집합을 얻을 수 있다.  이 점수집합에서의 값에 따라 각 스태프들에게 14개의 칩을 나눠주는데,  집합 내에서 가장 큰 점수를 가진 후보 스태프에게 1개의 칩을 주고, 집합 내에서 두번째로 점수가 큰 후보 스태프에게 1개의 칩을, ... 14번째로 점수가 큰 후보 스태프에게 1개의 칩을 준다. 최종적으로 스태프마다 득표수에 따라 칩의 개수가 다르게 지급될 것이다. 이것이 바로 ALPS식 투표이다. 성진은 스태프가 가진 칩의 개수에 비례해서 수고비를 지급하기로 했다. 신비롭게도, 점수집합에 있는 실수들은 항상 서로 다르도록 투표결과가 나온다고 한다.

우리는 각 스태프마다 몇개의 표를 얻었는지를 알고있다. 이 득표수를 토대로, ALPS식 투표를 수행하게 된 후, 각 스태프가 받을 칩의 개수를 구하는 프로그램을 작성하시오.

입력

첫번째 줄에는 전대프연 대회에 참가한 참가자들의 수 X( 1 ≤ X ≤ 2,500,000) 이 주어진다. 두번째 줄에는 전대프연에 참가한 스태프의 수 N (0 ≤ N ≤ 10) 이 주어진다.

다음 N개의 줄에 걸쳐 각 스태프의 정보 -스태프의 이름(항상 대문자 알파벳이다.)과 그 스태프가 받은 득표수- 가 공백을 사이에 두고 주어진다.

출력

득표율이 전체의 5% 이상인 스태프에 대해, 스태프의 이름과 그 스태프가 받은 칩의 개수를 한줄에 하나씩 출력한다. 출력하는 순서는 스태프 이름의 사전순이여야한다.

예제 입력 1

235217
3
A 107382
C 18059
B 43265

예제 출력 1

A 9
B 4
C 1
W3sicHJvYmxlbV9pZCI6IjI4MTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJBTFBTXHVjMmRkIFx1ZDIyY1x1ZDQ1YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODA0XHViMzAwXHVkNTA0XHVjNWYwKFx1YzgwNFx1YWQ2ZCBcdWIzMDBcdWQ1NTlcdWMwZGQgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YjMwMFx1ZDY4YyBcdWIzZDlcdWM1NDRcdWI5YWMmbmJzcDtcdWM1ZjBcdWQ1NjkpXHVjNWQwXHVjMTFjXHViMjk0IFx1YjllNFx1YjE0NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjXHViOTdjIFx1YzVmMFx1YjJlNC4gXHVjNjJjXHVkNTc0XHViM2M0IFx1YmIzNFx1YzBhY1x1ZDc4OCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTVjIFx1YzgwNFx1YjMwMFx1ZDUwNFx1YzVmMCBcdWQ2OGNcdWM3YTUgXHVjMTMxXHVjOWM0XHVjNzQwIFx1YzIxOFx1YWNlMFx1ZDU3NFx1YzkwMCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjMjE4XHVhY2UwXHViZTQ0XHViOTdjJm5ic3A7XHVjOGZjXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YmE4N1x1YmE4NyBcdWMyYTRcdWQwZGNcdWQ1MDRcdWIyOTQgXHVjNzdjXHVjNzQ0IFx1YzVmNFx1YzJlY1x1ZDc4OFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzEzMVx1YzljNFx1Yzc0MCBcdWM3N2NcdWM3NDQgXHVjNWY0XHVjMmVjXHVkNzg4IFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGNcdWI5Y2MgXHVjOGZjXHVhZTMwXHViODVjXHVkNTg4XHViMmU0LiZuYnNwO1x1ZDU1OFx1YzljMFx1YjljYyBcdWM3N2NcdWM3NDQgXHViYjM0XHVjOWM0XHVjN2E1Jm5ic3A7XHVjNWY0XHVjMmVjXHVkNzg4IFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWFjZmMgXHViMzVjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNWQwXHVhYzhjIFx1YzIxOFx1YWNlMFx1YmU0NFx1Yjk3YyBcdWI2MTFcdWFjMTlcdWM3NzQmbmJzcDtcdWM4ZmNcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YmQ4OFx1YWNmNVx1ZDNjOVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHViYmZjXHVjNzQ0IFx1ZDU1YyZuYnNwO1x1YzEzMVx1YzljNFx1Yzc0MCBcdWMyMThcdWFjZTBcdWJlNDRcdWI5N2MgXHViYzFiXHVjNzQ0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCZuYnNwO1x1YzEyMFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMmbmJzcDtBTFBTKEFsbGVncm8gTGVhZGVyIFBpY2tpbmcgU3lzdGVtKSBcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHVhZTMwXHViODVjIFx1YWNiMFx1YzJlY1x1ZDU4OFx1YjJlNC4gQUxQU1x1YjI5NCBcdWM3NzRcdWI5ODRcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNzc0XHViNGVmXHVjNzc0LCBcdWM1NDRcdWM4ZmMgXHVjNzIwXHVjZjhjXHVkNTU4XHVhY2UwIFx1YmU2MFx1Yjk3NFx1YWM4YyZuYnNwO1x1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWMxMjBcdWJjYzRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWMxMjAgXHViMzAwXHVkNjhjIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjRlNFx1Yzc0MCZuYnNwOyAmcXVvdDtcdWMyMThcdWFjZTBcdWJlNDRcdWI5N2MgXHViYzFiXHVjNzQ0IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMGRjXHVkNTA0JnF1b3Q7IFx1ZDU1Y1x1YmE4NVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NzQmbmJzcDtcdWQyMmNcdWQ0NWNcdWI5N2MgXHVkNTVjXHViMmU0LiAoXHVjYzM4XHVhYzAwXHVjNzkwXHVhYzAwIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuKSZuYnNwO1x1Yzc3NCBcdWQyMmNcdWQ0NWNcdWFjYjBcdWFjZmMsIFx1YzgwNFx1Y2NiNCZuYnNwO1x1YjMwMFx1ZDY4YyZuYnNwO1x1Y2MzOFx1YWMwMFx1Yzc5MFx1Yzc1OCA1JSBcdWJiZjhcdWI5Y2NcdWM3NTggXHViNGRkXHVkNDVjXHViOTdjIFx1YzViYlx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNWY0XHVjMmVjXHVkNzg4IFx1Yzc3Y1x1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzJhNFx1ZDBkY1x1ZDUwNFx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWQ2YzRcdWJjZjRcdWM1ZDBcdWMxMWMgXHVjODFjXHVjNjc4XHVkNTc0XHViYzg0XHViOWIwXHViMmU0LiBcdWM3NzRcdWM4MWMgXHViMGE4XHVjNzQwIFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YjljOFx1YjJlNCwgXHViYzFiXHVjNzQwIFx1YjRkZFx1ZDQ1Y1x1YzIxOFx1Yjk3YyAxXHViODVjIFx1YjA5OFx1YjIwOCZuYnNwO1x1YWMxMiwgMlx1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyLi4uIDE0XHViODVjIFx1YjA5OFx1YjIwOCBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVhZDZjXHVkNTVjIDE0XHVhYzFjXHVjNzU4IFx1YzJlNFx1YzIxOFx1YWMwMCBcdWFkZjggXHVjMmE0XHVkMGRjXHVkNTA0XHVjNzU4ICYjMzk7XHVjODEwXHVjMjE4JiMzOTtcdWI0ZTRcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgMTQgKiAoXHVkNmM0XHViY2Y0IFx1YzJhNFx1ZDBkY1x1ZDUwNFx1Yzc1OCBcdWJhODVcdWMyMTgpIFx1YWMxY1x1Yzc1OCBcdWMyZTRcdWMyMThcdWI5N2MgXHVhYzAwXHVjOWM0Jm5ic3A7XHVjODEwXHVjMjE4XHVjOWQxXHVkNTY5XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOyZuYnNwO1x1Yzc3NCBcdWM4MTBcdWMyMThcdWM5ZDFcdWQ1NjlcdWM1ZDBcdWMxMWNcdWM3NTggXHVhYzEyXHVjNWQwIFx1YjUzMFx1Yjc3YyZuYnNwO1x1YWMwMSBcdWMyYTRcdWQwZGNcdWQ1MDRcdWI0ZTRcdWM1ZDBcdWFjOGMgMTRcdWFjMWNcdWM3NTgmbmJzcDtcdWNlNjlcdWM3NDQgXHViMDk4XHViMjIwXHVjOGZjXHViMjk0XHViMzcwLCZuYnNwOyZuYnNwO1x1YzlkMVx1ZDU2OSBcdWIwYjRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhYzAwXHVjOWM0Jm5ic3A7XHVkNmM0XHViY2Y0IFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YzVkMFx1YWM4YyAxXHVhYzFjXHVjNzU4IFx1Y2U2OVx1Yzc0NCBcdWM4ZmNcdWFjZTAsJm5ic3A7XHVjOWQxXHVkNTY5IFx1YjBiNFx1YzVkMFx1YzExYyZuYnNwO1x1YjQ1MFx1YmM4OFx1YzlmOFx1Yjg1YyBcdWM4MTBcdWMyMThcdWFjMDAgXHVkMDcwJm5ic3A7XHVkNmM0XHViY2Y0IFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YzVkMFx1YWM4YyAxXHVhYzFjXHVjNzU4IFx1Y2U2OVx1Yzc0NCwgLi4uIDE0XHViYzg4XHVjOWY4XHViODVjIFx1YzgxMFx1YzIxOFx1YWMwMCBcdWQwNzAmbmJzcDtcdWQ2YzRcdWJjZjQgXHVjMmE0XHVkMGRjXHVkNTA0XHVjNWQwXHVhYzhjIDFcdWFjMWNcdWM3NTggXHVjZTY5XHVjNzQ0IFx1YzkwMFx1YjJlNC4gXHVjZDVjXHVjODg1XHVjODAxXHVjNzNjXHViODVjIFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YjljOFx1YjJlNCBcdWI0ZGRcdWQ0NWNcdWMyMThcdWM1ZDAgXHViNTMwXHViNzdjIFx1Y2U2OVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHViMmU0XHViOTc0XHVhYzhjIFx1YzljMFx1YWUwOVx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuJm5ic3A7XHVjNzc0XHVhYzgzXHVjNzc0IFx1YmMxNFx1Yjg1YyBBTFBTXHVjMmRkIFx1ZDIyY1x1ZDQ1Y1x1Yzc3NFx1YjJlNC4mbmJzcDtcdWMxMzFcdWM5YzRcdWM3NDAgXHVjMmE0XHVkMGRjXHVkNTA0XHVhYzAwIFx1YWMwMFx1YzljNCZuYnNwO1x1Y2U2OVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM1ZDAgXHViZTQ0XHViODQwXHVkNTc0XHVjMTFjIFx1YzIxOFx1YWNlMFx1YmU0NFx1Yjk3YyZuYnNwO1x1YzljMFx1YWUwOVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuJm5ic3A7XHVjMmUwXHViZTQ0XHViODZkXHVhYzhjXHViM2M0LCBcdWM4MTBcdWMyMThcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJlNFx1YzIxOFx1YjRlNFx1Yzc0MCBcdWQ1NmRcdWMwYzEmbmJzcDtcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViM2M0XHViODVkIFx1ZDIyY1x1ZDQ1Y1x1YWNiMFx1YWNmY1x1YWMwMCBcdWIwOThcdWM2MjhcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWIyOTQgXHVhYzAxIFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YjljOFx1YjJlNCBcdWJhODdcdWFjMWNcdWM3NTggXHVkNDVjXHViOTdjIFx1YzViYlx1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM1NGNcdWFjZTBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI0ZGRcdWQ0NWNcdWMyMThcdWI5N2MgXHVkMWEwXHViMzAwXHViODVjLCBBTFBTXHVjMmRkIFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWMyMThcdWQ1ODlcdWQ1NThcdWFjOGMgXHViNDFjIFx1ZDZjNCwgXHVhYzAxIFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YWMwMCBcdWJjMWJcdWM3NDQgXHVjZTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCZuYnNwO1x1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MDRcdWIzMDBcdWQ1MDRcdWM1ZjAgXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1YyBcdWNjMzhcdWFjMDBcdWM3OTBcdWI0ZTRcdWM3NTggXHVjMjE4IFgoIDEgJmxlOyBYICZsZTsgMiw1MDAsMDAwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgwNFx1YjMwMFx1ZDUwNFx1YzVmMFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NWMgXHVjMmE0XHVkMGRjXHVkNTA0XHVjNzU4IFx1YzIxOCBOICgwICZsZTsgTiAmbGU7IDEwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSZuYnNwO1x1YzJhNFx1ZDBkY1x1ZDUwNFx1Yzc1OCBcdWM4MTVcdWJjZjQgLVx1YzJhNFx1ZDBkY1x1ZDUwNFx1Yzc1OCBcdWM3NzRcdWI5ODQoXHVkNTZkXHVjMGMxIFx1YjMwMFx1YmIzOFx1Yzc5MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NzRcdWIyZTQuKVx1YWNmYyBcdWFkZjggXHVjMmE0XHVkMGRjXHVkNTA0XHVhYzAwIFx1YmMxYlx1Yzc0MCBcdWI0ZGRcdWQ0NWNcdWMyMTgtJm5ic3A7XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjRkZFx1ZDQ1Y1x1YzcyOFx1Yzc3NCBcdWM4MDRcdWNjYjRcdWM3NTggNSUgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YzJhNFx1ZDBkY1x1ZDUwNFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWFjZmMgXHVhZGY4IFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YWMwMCBcdWJjMWJcdWM3NDAgXHVjZTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWQ1NWNcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjI5NCBcdWMyYTRcdWQwZGNcdWQ1MDQgXHVjNzc0XHViOTg0XHVjNzU4IFx1YzBhY1x1YzgwNFx1YzIxY1x1Yzc3NFx1YzVlY1x1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODE3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRFx1MjAxOUhPTkRUIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgYmVnaW5uaW5nIG9mIERlY2VtYmVyLCBwYXJsaWFtZW50YXJ5IGVsZWN0aW9ucyB3ZXJlIGhlbGQgaW4gb3VyIGNvdW50cnkuIENyb2F0aWEgaXMgZGl2aWRlZCBpbiAxMCBlbGVjdGlvbiByZWdpb25zLiBGcm9tIGVhY2ggcmVnaW9uLCAxNCBwYXJsaWFtZW50YXJ5IHJlcHJlc2VudGF0aXZlcyBhcmUgZWxlY3RlZC4gRWFjaCBvZiB0aGUgdm90ZXJzIGlzIHZvdGluZyBmb3Igb25lIG9mIHRoZSBmZXcgcGFydGllcy4gQWZ0ZXIgdm90aW5nLCB0aGUgcmVwcmVzZW50YXRpdmVzIGFyZSBlbGVjdGVkIHVzaW5nIHRoZSBEJiMzOTtIb25kdCAoRCZxdW90O09udCkgbWV0aG9kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5CeSB0aGlzIG1ldGhvZCwgZmlyc3Qgd2Ugc2VsZWN0IHBhcnRpZXMgd2hpY2ggZ2F0aGVyZWQgYXQgbGVhc3QgNSUgb2YgdGhlIHZvdGVzLiBOdW1iZXIgb2Ygdm90ZXMgb2YgZWFjaCBvZiB0aGUgc2VsZWN0ZWQgcGFydGllcyBpcyB0aGVuIGRpdmlkZWQgYnkgZXZlcnkgbnVtYmVyIGZyb20gMSB0byAxNC4gSW4gdGhpcyB3YXkgd2UgYXNzaWduIDE0IHJhdGlvbmFsIG51bWJlcnMgLSBsZXQmcnNxdW87cyBjYWxsIHRoZW0gJmxzcXVvO3Njb3JlcyZyc3F1bzsgLSB0byBlYWNoIG9mIHRoZSBwYXJ0aWVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaXJzdCBvZiB0aGUgMTQgcmVwcmVzZW50YXRpdmVzIGluIGEgcmVnaW9uIGlzIGNob3NlbiBmcm9tIGEgcGFydHkgd2l0aCB0aGUgbGFyZ2VzdCBzY29yZS4gU2Vjb25kIHJlcHJlc2VudGF0aXZlIGlzIHNlbGVjdGVkIGZyb20gYSBwYXJ0eSB3aXRoIHRoZSBzZWNvbmQgbGFyZ2VzdCBzY29yZS4gVGhlIHRoaXJkLi4uIFRoaXMgcHJvY2VkdXJlIGNvbnRpbnVlcyB1bnRpbCBhbGwgb2YgdGhlIDE0IHBsYWNlcyBhcmUgZWxlY3RlZC4gUmVtYXJrOiBUaGVyZSB3aWxsIGFsd2F5cyBiZSBhIHVuaXF1ZSB3YXkgdG8gZWxlY3QgdGhlIHJlcHJlc2VudGF0aXZlcywgaS5lLiBubyB0d28gc2NvcmVzIHdpbGwgYmUgZXF1YWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgdG90YWwgbnVtYmVyIG9mIHZvdGVycyBhbmQgbnVtYmVyIG9mIHZvdGVzIGVhY2ggcGFydHkgZ2FpbmVkLCBkZXRlcm1pbmVzIGhvdyBtYW55IHBvbGl0aWNpYW5zIHdlcmUgZWxlY3RlZCBhcyByZWdpb24gcmVwcmVzZW50YXRpdmVzIGZyb20gZWFjaCBwYXJ0eS4gU29tZSBwYXJ0aWVzIGhhdmUgZ2FpbmVkIG5lZ2xpZ2libGUgbnVtYmVyIG9mIHZvdGVzIGFuZCB3aWxsIG5vdCBiZSBpbiB0aGUgaW5wdXQgLSB0aGF0IGlzIHRoZSByZWFzb24gdGhhdCB0aGUgdG90YWwgbnVtYmVyIG9mIHZvdGVycyBtaWdodCBub3QgYmUgZXF1YWwgdG8gdGhlIHN1bSBvZiBsaXN0IHZvdGVzIGluIHRoZSBpbnB1dC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIFggKDEgJmxlOyBYICZsZTsgMiA1MDAgMDAwKSwgdG90YWwgbnVtYmVyIG9mIHZvdGVycyBpbiB0aGUgcmVnaW9uLiBTZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgTiAoMCAmbGU7IE4gJmxlOyAxMCksIG51bWJlciBvZiBwYXJ0aWVzIHdlIGFyZSBjb25zaWRlcmluZy4gTmV4dCBOIGxpbmVzIGNvbnRhaW4gdHdvIHBvc2l0aXZlIGludGVnZXJzIGRpdmlkZWQgYnkgYSBzaW5nbGUgc3BhY2U6IHBhcnR5IGlkZW50aWZpZXIgKGNhcGl0YWwgbGV0dGVyIG9mIEVuZ2xpc2ggYWxwaGFiZXQpIGFuZCBhIHBvc2l0aXZlIGludGVnZXIgRyAoMCAmbGU7IEcgJmxlOyAyNTAgMDAwKSwgbnVtYmVyIG9mIHZvdGVzIGdhaW5lZCBieSB0aGF0IHBhcnR5LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBpcyBjb25zaXN0ZWQgb2YgbnVtYmVyIG9mIGxpbmVzIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgcGFydGllcyB3aGljaCBoYWQgYXQgbGVhc3QgNSUgb2YgdGhlIHZvdGVzLiBGb3IgZWFjaCBvZiB0aGVzZSBwYXJ0aWVzLCBwcmludCBhIHBhcnR5IGlkZW50aWZpZXIgYW5kIGEgbnVtYmVyIG9mIHBhcmxpYW1lbnRhcnkgcmVwcmVzZW50YXRpdmVzIGVsZWN0ZWQgZnJvbSB0aGF0IHBhcnR5LiBMaW5lcyBzaG91bGQgYmUgc29ydGVkIGJ5IGlkZW50aWZpZXJzLCBhbHBoYWJldGljYWx5LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #3 2번