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

문제

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

고민을 한 성진은 수고비를 받을 사람을 선출하는 방식으로 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

예제 입력 2

245143
4
F 14845
A 104516
B 52652
C 14161

예제 출력 2

A 8
B 4
C 1
F 1

예제 입력 3

206278
5
D 44687
A 68188
C 7008
B 48377
G 9665

예제 출력 3

A 6
B 4
D 4
W3sicHJvYmxlbV9pZCI6IjI4MTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJBTFBTXHVjMmRkIFx1ZDIyY1x1ZDQ1YyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODA0XHViMzAwXHVkNTA0XHVjNWYwKFx1YzgwNFx1YWQ2ZCBcdWIzMDBcdWQ1NTlcdWMwZGQgXHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkIFx1YjMwMFx1ZDY4YyBcdWIzZDlcdWM1NDRcdWI5YWMmbmJzcDtcdWM1ZjBcdWQ1NjkpXHVjNWQwXHVjMTFjXHViMjk0IFx1YjllNFx1YjE0NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHViMzAwXHVkNjhjXHViOTdjIFx1YzVmMFx1YjJlNC4gXHVjNjJjXHVkNTc0XHViM2M0IFx1YmIzNFx1YzBhY1x1ZDc4OCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTVjIFx1YzgwNFx1YjMwMFx1ZDUwNFx1YzVmMCBcdWQ2OGNcdWM3YTUgXHVjMTMxXHVjOWM0XHVjNzQwIFx1YzIxOFx1YWNlMFx1ZDU3NFx1YzkwMCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjMjE4XHVhY2UwXHViZTQ0XHViOTdjJm5ic3A7XHVjOGZjXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YmE4N1x1YmE4NyBcdWMyYTRcdWQwZGNcdWQ1MDRcdWIyOTQgXHVjNzdjXHVjNzQ0IFx1YzVmNFx1YzJlY1x1ZDc4OFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzEzMVx1YzljNFx1Yzc0MCBcdWM3N2NcdWM3NDQgXHVjNWY0XHVjMmVjXHVkNzg4IFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWM1ZDBcdWFjOGNcdWI5Y2MgXHVjOGZjXHVhZTMwXHViODVjXHVkNTg4XHViMmU0LiZuYnNwO1x1ZDU1OFx1YzljMFx1YjljYyBcdWM3N2NcdWM3NDQgXHViYjM0XHVjOWM0XHVjN2E1Jm5ic3A7XHVjNWY0XHVjMmVjXHVkNzg4IFx1ZDU1YyBcdWMwYWNcdWI3OGNcdWFjZmMgXHViMzVjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNWQwXHVhYzhjIFx1YzIxOFx1YWNlMFx1YmU0NFx1Yjk3YyBcdWI2MTFcdWFjMTlcdWM3NzQmbmJzcDtcdWM4ZmNcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YmQ4OFx1YWNmNVx1ZDNjOVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2UwXHViYmZjXHVjNzQ0IFx1ZDU1YyZuYnNwO1x1YzEzMVx1YzljNFx1Yzc0MCBcdWMyMThcdWFjZTBcdWJlNDRcdWI5N2MgXHViYzFiXHVjNzQ0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCZuYnNwO1x1YzEyMFx1Y2Q5Y1x1ZDU1OFx1YjI5NCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMmbmJzcDtBTFBTKEFsbGVncm8gTGVhZGVyIFBpY2tpbmcgU3lzdGVtKSBcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHVhZTMwXHViODVjIFx1YWNiMFx1YzJlY1x1ZDU4OFx1YjJlNC4gQUxQU1x1YjI5NCBcdWM3NzRcdWI5ODRcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNzc0XHViNGVmXHVjNzc0LCBcdWM1NDRcdWM4ZmMgXHVjNzIwXHVjZjhjXHVkNTU4XHVhY2UwIFx1YmU2MFx1Yjk3NFx1YWM4YyZuYnNwO1x1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0NCBcdWMxMjBcdWJjYzRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWMxMjAgXHViMzAwXHVkNjhjIFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YjRlNFx1Yzc0MCZuYnNwOyAmcXVvdDtcdWMyMThcdWFjZTBcdWJlNDRcdWI5N2MgXHViYzFiXHVjNzQ0IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVkMGRjXHVkNTA0JnF1b3Q7IFx1ZDU1YyBcdWJhODVcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTc0Jm5ic3A7XHVkMjJjXHVkNDVjXHViOTdjIFx1ZDU1Y1x1YjJlNC4gKFx1Y2MzOFx1YWMwMFx1Yzc5MFx1YWMwMCBcdWQyMmNcdWQ0NWNcdWI5N2MgXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LikmbmJzcDtcdWM3NzQgXHVkMjJjXHVkNDVjXHVhY2IwXHVhY2ZjLCBcdWM4MDRcdWNjYjQmbmJzcDtcdWIzMDBcdWQ2OGMmbmJzcDtcdWNjMzhcdWFjMDBcdWM3OTBcdWM3NTggNSUgXHViYmY4XHViOWNjXHVjNzU4IFx1YjRkZFx1ZDQ1Y1x1Yjk3YyBcdWM1YmJcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWM3N2NcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWM3NzRcdWJiYzBcdWI4NWMgXHVkNmM0XHViY2Y0XHVjNWQwXHVjMTFjIFx1YzgxY1x1YzY3OFx1ZDU3NFx1YmM4NFx1YjliMFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YjBhOFx1Yzc0MCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWI5YzhcdWIyZTQsIFx1YmMxYlx1Yzc0MCBcdWI0ZGRcdWQ0NWNcdWMyMThcdWI5N2MgMVx1Yjg1YyBcdWIwOThcdWIyMDgmbmJzcDtcdWFjMTIsIDJcdWI4NWMgXHViMDk4XHViMjA4IFx1YWMxMi4uLiAxNFx1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YWQ2Y1x1ZDU1YyAxNFx1YWMxY1x1Yzc1OCBcdWMyZTRcdWMyMThcdWFjMDAgXHVhZGY4IFx1YzJhNFx1ZDBkY1x1ZDUwNFx1Yzc1OCAmIzM5O1x1YzgxMFx1YzIxOCYjMzk7XHViNGU0XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViODA3XHVhYzhjIDE0ICogKFx1ZDZjNFx1YmNmNCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWM3NTggXHViYTg1XHVjMjE4KSBcdWFjMWNcdWM3NTggXHVjMmU0XHVjMjE4XHViOTdjIFx1YWMwMFx1YzljNCZuYnNwO1x1YzgxMFx1YzIxOFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDsmbmJzcDtcdWM3NzQgXHVjODEwXHVjMjE4XHVjOWQxXHVkNTY5XHVjNWQwXHVjMTFjXHVjNzU4IFx1YWMxMlx1YzVkMCBcdWI1MzBcdWI3N2MmbmJzcDtcdWFjMDEgXHVjMmE0XHVkMGRjXHVkNTA0XHViNGU0XHVjNWQwXHVhYzhjIDE0XHVhYzFjXHVjNzU4Jm5ic3A7XHVjZTY5XHVjNzQ0IFx1YjA5OFx1YjIyMFx1YzhmY1x1YjI5NFx1YjM3MCwmbmJzcDsmbmJzcDtcdWM5ZDFcdWQ1NjkgXHViMGI0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjODEwXHVjMjE4XHViOTdjIFx1YWMwMFx1YzljNCZuYnNwO1x1ZDZjNFx1YmNmNCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWM1ZDBcdWFjOGMgMVx1YWMxY1x1Yzc1OCBcdWNlNjlcdWM3NDQgXHVjOGZjXHVhY2UwLCZuYnNwO1x1YzlkMVx1ZDU2OSBcdWIwYjRcdWM1ZDBcdWMxMWMmbmJzcDtcdWI0NTAgXHViYzg4XHVjOWY4XHViODVjIFx1YzgxMFx1YzIxOFx1YWMwMCBcdWQwNzAmbmJzcDtcdWQ2YzRcdWJjZjQgXHVjMmE0XHVkMGRjXHVkNTA0XHVjNWQwXHVhYzhjIDFcdWFjMWNcdWM3NTggXHVjZTY5XHVjNzQ0LCAuLi4gMTRcdWJjODhcdWM5ZjhcdWI4NWMgXHVjODEwXHVjMjE4XHVhYzAwIFx1ZDA3MCZuYnNwO1x1ZDZjNFx1YmNmNCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWM1ZDBcdWFjOGMgMVx1YWMxY1x1Yzc1OCBcdWNlNjlcdWM3NDQgXHVjOTAwXHViMmU0LiBcdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMmE0XHVkMGRjXHVkNTA0XHViOWM4XHViMmU0IFx1YjRkZFx1ZDQ1Y1x1YzIxOFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVjZTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWIyZTRcdWI5NzRcdWFjOGMgXHVjOWMwXHVhZTA5XHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4mbmJzcDtcdWM3NzRcdWFjODNcdWM3NzQgXHViYzE0XHViODVjIEFMUFNcdWMyZGQgXHVkMjJjXHVkNDVjXHVjNzc0XHViMmU0LiZuYnNwO1x1YzEzMVx1YzljNFx1Yzc0MCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWFjMDAgXHVhYzAwXHVjOWM0Jm5ic3A7XHVjZTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NzRcdWMxMWMgXHVjMjE4XHVhY2UwXHViZTQ0XHViOTdjJm5ic3A7XHVjOWMwXHVhZTA5XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4mbmJzcDtcdWMyZTBcdWJlNDRcdWI4NmRcdWFjOGNcdWIzYzQsIFx1YzgxMFx1YzIxOFx1YzlkMVx1ZDU2OVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmU0XHVjMjE4XHViNGU0XHVjNzQwIFx1ZDU2ZFx1YzBjMSZuYnNwO1x1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIzYzRcdWI4NWQgXHVkMjJjXHVkNDVjXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YjA5OFx1YzYyOFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YjI5NCBcdWFjMDEgXHVjMmE0XHVkMGRjXHVkNTA0XHViOWM4XHViMmU0IFx1YmE4N1x1YWMxY1x1Yzc1OCBcdWQ0NWNcdWI5N2MgXHVjNWJiXHVjNWM4XHViMjk0XHVjOWMwXHViOTdjIFx1YzU0Y1x1YWNlMFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjRkZFx1ZDQ1Y1x1YzIxOFx1Yjk3YyBcdWQxYTBcdWIzMDBcdWI4NWMsIEFMUFNcdWMyZGQgXHVkMjJjXHVkNDVjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YWM4YyBcdWI0MWMgXHVkNmM0LCBcdWFjMDEgXHVjMmE0XHVkMGRjXHVkNTA0XHVhYzAwIFx1YmMxYlx1Yzc0NCBcdWNlNjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCZuYnNwO1x1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MDRcdWIzMDBcdWQ1MDRcdWM1ZjAgXHViMzAwXHVkNjhjXHVjNWQwIFx1Y2MzOFx1YWMwMFx1ZDU1YyBcdWNjMzhcdWFjMDBcdWM3OTBcdWI0ZTRcdWM3NTggXHVjMjE4IFgoIDEgJmxlOyBYICZsZTsgMiw1MDAsMDAwKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MDRcdWIzMDBcdWQ1MDRcdWM1ZjBcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTVjIFx1YzJhNFx1ZDBkY1x1ZDUwNFx1Yzc1OCBcdWMyMTggTiAoMCAmbGU7IE4gJmxlOyAxMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjMDEmbmJzcDtcdWMyYTRcdWQwZGNcdWQ1MDRcdWM3NTggXHVjODE1XHViY2Y0IC1cdWMyYTRcdWQwZGNcdWQ1MDRcdWM3NTggXHVjNzc0XHViOTg0KFx1ZDU2ZFx1YzBjMSBcdWIzMDBcdWJiMzhcdWM3OTAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0XHViMmU0LilcdWFjZmMgXHVhZGY4IFx1YzJhNFx1ZDBkY1x1ZDUwNFx1YWMwMCBcdWJjMWJcdWM3NDAgXHViNGRkXHVkNDVjXHVjMjE4LSZuYnNwO1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI0ZGRcdWQ0NWNcdWM3MjhcdWM3NzQgXHVjODA0XHVjY2I0XHVjNzU4IDUlIFx1Yzc3NFx1YzBjMVx1Yzc3OCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWM3NTggXHVjNzc0XHViOTg0XHVhY2ZjIFx1YWRmOCBcdWMyYTRcdWQwZGNcdWQ1MDRcdWFjMDAgXHViYzFiXHVjNzQwIFx1Y2U2OVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVkNTVjXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIyOTQgXHVjMmE0XHVkMGRjXHVkNTA0IFx1Yzc3NFx1Yjk4NFx1Yzc1OCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3NzRcdWM1ZWNcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjgxNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRcdTIwMTlIT05EVCIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIGJlZ2lubmluZyBvZiBEZWNlbWJlciwgcGFybGlhbWVudGFyeSBlbGVjdGlvbnMgd2VyZSBoZWxkIGluIG91ciBjb3VudHJ5LiBDcm9hdGlhIGlzIGRpdmlkZWQgaW4gMTAgZWxlY3Rpb24gcmVnaW9ucy4gRnJvbSBlYWNoIHJlZ2lvbiwgMTQgcGFybGlhbWVudGFyeSByZXByZXNlbnRhdGl2ZXMgYXJlIGVsZWN0ZWQuIEVhY2ggb2YgdGhlIHZvdGVycyBpcyB2b3RpbmcgZm9yIG9uZSBvZiB0aGUgZmV3IHBhcnRpZXMuIEFmdGVyIHZvdGluZywgdGhlIHJlcHJlc2VudGF0aXZlcyBhcmUgZWxlY3RlZCB1c2luZyB0aGUgRCYjMzk7SG9uZHQgKEQmcXVvdDtPbnQpIG1ldGhvZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QnkgdGhpcyBtZXRob2QsIGZpcnN0IHdlIHNlbGVjdCBwYXJ0aWVzIHdoaWNoIGdhdGhlcmVkIGF0IGxlYXN0IDUlIG9mIHRoZSB2b3Rlcy4gTnVtYmVyIG9mIHZvdGVzIG9mIGVhY2ggb2YgdGhlIHNlbGVjdGVkIHBhcnRpZXMgaXMgdGhlbiBkaXZpZGVkIGJ5IGV2ZXJ5IG51bWJlciBmcm9tIDEgdG8gMTQuIEluIHRoaXMgd2F5IHdlIGFzc2lnbiAxNCByYXRpb25hbCBudW1iZXJzIC0gbGV0JnJzcXVvO3MgY2FsbCB0aGVtICZsc3F1bztzY29yZXMmcnNxdW87IC0gdG8gZWFjaCBvZiB0aGUgcGFydGllcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rmlyc3Qgb2YgdGhlIDE0IHJlcHJlc2VudGF0aXZlcyBpbiBhIHJlZ2lvbiBpcyBjaG9zZW4gZnJvbSBhIHBhcnR5IHdpdGggdGhlIGxhcmdlc3Qgc2NvcmUuIFNlY29uZCByZXByZXNlbnRhdGl2ZSBpcyBzZWxlY3RlZCBmcm9tIGEgcGFydHkgd2l0aCB0aGUgc2Vjb25kIGxhcmdlc3Qgc2NvcmUuIFRoZSB0aGlyZC4uLiBUaGlzIHByb2NlZHVyZSBjb250aW51ZXMgdW50aWwgYWxsIG9mIHRoZSAxNCBwbGFjZXMgYXJlIGVsZWN0ZWQuIFJlbWFyazogVGhlcmUgd2lsbCBhbHdheXMgYmUgYSB1bmlxdWUgd2F5IHRvIGVsZWN0IHRoZSByZXByZXNlbnRhdGl2ZXMsIGkuZS4gbm8gdHdvIHNjb3JlcyB3aWxsIGJlIGVxdWFsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIHRvdGFsIG51bWJlciBvZiB2b3RlcnMgYW5kIG51bWJlciBvZiB2b3RlcyBlYWNoIHBhcnR5IGdhaW5lZCwgZGV0ZXJtaW5lcyBob3cgbWFueSBwb2xpdGljaWFucyB3ZXJlIGVsZWN0ZWQgYXMgcmVnaW9uIHJlcHJlc2VudGF0aXZlcyBmcm9tIGVhY2ggcGFydHkuIFNvbWUgcGFydGllcyBoYXZlIGdhaW5lZCBuZWdsaWdpYmxlIG51bWJlciBvZiB2b3RlcyBhbmQgd2lsbCBub3QgYmUgaW4gdGhlIGlucHV0IC0gdGhhdCBpcyB0aGUgcmVhc29uIHRoYXQgdGhlIHRvdGFsIG51bWJlciBvZiB2b3RlcnMgbWlnaHQgbm90IGJlIGVxdWFsIHRvIHRoZSBzdW0gb2YgbGlzdCB2b3RlcyBpbiB0aGUgaW5wdXQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBYICgxICZsZTsgWCAmbGU7IDIgNTAwIDAwMCksIHRvdGFsIG51bWJlciBvZiB2b3RlcnMgaW4gdGhlIHJlZ2lvbi4gU2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDAgJmxlOyBOICZsZTsgMTApLCBudW1iZXIgb2YgcGFydGllcyB3ZSBhcmUgY29uc2lkZXJpbmcuIE5leHQgTiBsaW5lcyBjb250YWluIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBkaXZpZGVkIGJ5IGEgc2luZ2xlIHNwYWNlOiBwYXJ0eSBpZGVudGlmaWVyIChjYXBpdGFsIGxldHRlciBvZiBFbmdsaXNoIGFscGhhYmV0KSBhbmQgYSBwb3NpdGl2ZSBpbnRlZ2VyIEcgKDAgJmxlOyBHICZsZTsgMjUwIDAwMCksIG51bWJlciBvZiB2b3RlcyBnYWluZWQgYnkgdGhhdCBwYXJ0eS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgaXMgY29uc2lzdGVkIG9mIG51bWJlciBvZiBsaW5lcyBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHBhcnRpZXMgd2hpY2ggaGFkIGF0IGxlYXN0IDUlIG9mIHRoZSB2b3Rlcy4gRm9yIGVhY2ggb2YgdGhlc2UgcGFydGllcywgcHJpbnQgYSBwYXJ0eSBpZGVudGlmaWVyIGFuZCBhIG51bWJlciBvZiBwYXJsaWFtZW50YXJ5IHJlcHJlc2VudGF0aXZlcyBlbGVjdGVkIGZyb20gdGhhdCBwYXJ0eS4gTGluZXMgc2hvdWxkIGJlIHNvcnRlZCBieSBpZGVudGlmaWVycywgYWxwaGFiZXRpY2FseS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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