시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB198554848.485%

문제

상근이는 토끼 N마리를 키우고 있다. 그는 매일 매일 토끼에게 다양한 야채와 과일을 먹이로 주고 있었다. 그러나, 상근이의 토끼는 딸기를 가장 좋아한다. 하지만 겨울에는 딸기를 구하기가 매우 어렵고, 가격도 비싸다. 따라서 상근이는 일부 토끼에게만 딸기를 주기로 했다.

상근이 토끼의 이름은 숫자이고, 1번부터 N번이다. 상근이는 각 토끼가 먹는 딸기의 양을 기록을 하기 위해서 다음과 같은 방법을 이용한다.

매일 상근이는 딸기 S개를 구매한다. 그러고 난 뒤, A번 토끼에게 첫 번째 딸기를, A+1번 토끼에게 두 번째 딸기를, A+2번 토끼에게 세 번째 딸기를,.... 준다.

모든 토끼는 비어있는 성냥갑을 가지고 있고, 이 성냥갑은 한 줄로 놓여져 있다.

K·K ≤ N을 만족하는 가장 큰 K를 고른다. 그 다음 첫 성냥갑부터 K개씩 그룹을 지어준다. 각 성냥갑의 앞에는 컵을 하나씩 놓는다. 이렇게 연속하는 K개 성냥갑과 컵을 블록이라고 한다.

토끼에게 딸기를 준 다음에, 상근이는 딸기를 받은 토끼의 성냥갑에 성냥을 넣는다. 이때, 어떤 블록에 모든 성냥갑에 성냥을 넣어야된다면, 성냥갑 대신에 컵에 성냥을 넣는다. 

위의 방법을 사용하면, 각 토끼가 지금까지 먹은 딸기의 수는 성냥갑과 컵에 들어있는 성냥의 수가 된다.

예를 들어, 위와 같이 토끼가 11마리 있다고하자. 그럼 N = 11이 된다. 이때, K를 구하면 K = 3이 된다. 따라서, 총 네 개의 블록이 있을 것이고, 마지막 블록에는 성냥갑이 2개만 있을 것이다. 만약, 상근이가 딸기를 6개 사왔고, 5번 토끼부터 딸기를 준다면, 성냥갑과 컵에 들어있는 성냥은 아래와 같이 된다.

토끼의 수 N이 주어지고, M일동안 구매한 딸기의 수와 토끼에게 준 방법이 주어진다. 이때, 상근이가 그날 성냥을 넣은 성냥갑과 컵에 들어있는 성냥의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 100000)

다음 M개 줄에는 각 날 상근이가 구매한 딸기의 수 S와 딸기를 주기 시작하는 토끼의 번호 A가 주어진다. (1 ≤ A ≤ N, 1 ≤ A+S–1 ≤ N)

출력

출력은 총 M개의 숫자를 출력해야 한다. k번째 줄에는 k번째 날에 성냥을 넣은 성냥갑과 컵에 들어있는 성냥의 수를 출력해야 한다.

예제 입력 1

11 3
6 5
3 1
11 1

예제 출력 1

4
1
6

예제 입력 2

16 3
2 2
12 3
6 11

예제 출력 2

2
7
3

힌트

예제 1의 경우에는 토끼가 11마리 있고, 블록이 4개있는 경우이다. (그림과 같은 경우)

첫째 날 상근이가 딸기를 주는 토끼의 번호는 5번부터 10번이다. 성냥갑 5,6,10번에는 성냥을 넣을 것이고, 세 번째 컵에 성냥갑을 넣는다. 첫째 날이기 때문에, 원래 성냥이 들어있는 성냥갑과 컵은 없다. 따라서 정답은 4가 된다.

둘째 날 상근이는 1번부터 3번토끼에게 딸기를 준다. 첫 번째 컵에 성냥을 넣으면 된다.

셋째 날에는 모든 토끼에게 딸기를 준다. 이런 경우에는 모든 컵에 성냥을 하나씩 넣으면 된다. 따라서, 정답은 6이 된다.

W3sicHJvYmxlbV9pZCI6IjI5NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxYTBcdWIwN2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQxYTBcdWIwN2MgTlx1YjljOFx1YjlhY1x1Yjk3YyBcdWQwYTRcdWM2YjBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWIyOTQgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWQxYTBcdWIwN2NcdWM1ZDBcdWFjOGMgXHViMmU0XHVjNTkxXHVkNTVjIFx1YzU3Y1x1Y2M0NFx1YzY0MCBcdWFjZmNcdWM3N2NcdWM3NDQgXHViYTM5XHVjNzc0XHViODVjIFx1YzhmY1x1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1ZDFhMFx1YjA3Y1x1YjI5NCBcdWI1MzhcdWFlMzBcdWI5N2MgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YWNhOFx1YzZiOFx1YzVkMFx1YjI5NCBcdWI1MzhcdWFlMzBcdWI5N2MgXHVhZDZjXHVkNTU4XHVhZTMwXHVhYzAwIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MzVcdWFjZTAsIFx1YWMwMFx1YWNhOVx1YjNjNCBcdWJlNDRcdWMyZjhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzdjXHViZDgwIFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4Y1x1YjljYyBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOGZjXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0IFx1ZDFhMFx1YjA3Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgXHVjMjJiXHVjNzkwXHVjNzc0XHVhY2UwLCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVkMWEwXHViMDdjXHVhYzAwIFx1YmEzOVx1YjI5NCBcdWI1MzhcdWFlMzBcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YWUzMFx1Yjg1ZFx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0XHVjNzdjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI1MzhcdWFlMzAgU1x1YWMxY1x1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YWNlMCBcdWIwOWMgXHViNGE0LCBBXHViYzg4IFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjUzOFx1YWUzMFx1Yjk3YywgQSsxXHViYzg4IFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YjUzOFx1YWUzMFx1Yjk3YywgQSsyXHViYzg4IFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YjUzOFx1YWUzMFx1Yjk3YywuLi4uIFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDFhMFx1YjA3Y1x1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzExXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWMxMzFcdWIwZTVcdWFjMTFcdWM3NDAgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5LJm1pZGRvdDtLICZsZTsgTlx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBLXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWNjYWIgXHVjMTMxXHViMGU1XHVhYzExXHViZDgwXHVkMTMwIEtcdWFjMWNcdWM1MjkgXHVhZGY4XHViOGY5XHVjNzQ0IFx1YzljMFx1YzViNFx1YzkwMFx1YjJlNC4gXHVhYzAxIFx1YzEzMVx1YjBlNVx1YWMxMVx1Yzc1OCBcdWM1NWVcdWM1ZDBcdWIyOTQgXHVjZWY1XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM1ZjBcdWMxOGRcdWQ1NThcdWIyOTQgS1x1YWMxYyBcdWMxMzFcdWIwZTVcdWFjMTFcdWFjZmMgXHVjZWY1XHVjNzQ0IFx1YmUxNFx1Yjg1ZFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOTAwIFx1YjJlNFx1Yzc0Y1x1YzVkMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjUzOFx1YWUzMFx1Yjk3YyBcdWJjMWJcdWM3NDAgXHVkMWEwXHViMDdjXHVjNzU4IFx1YzEzMVx1YjBlNVx1YWMxMVx1YzVkMCBcdWMxMzFcdWIwZTVcdWM3NDQgXHViMTIzXHViMjk0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzViNFx1YjVhNCBcdWJlMTRcdWI4NWRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YzEzMVx1YjBlNVx1YWMxMVx1YzVkMCBcdWMxMzFcdWIwZTVcdWM3NDQgXHViMTIzXHVjNWI0XHVjNTdjXHViNDFjXHViMmU0XHViYTc0LCBcdWMxMzFcdWIwZTVcdWFjMTEgXHViMzAwXHVjMmUwXHVjNWQwIFx1Y2VmNVx1YzVkMCBcdWMxMzFcdWIwZTVcdWM3NDQgXHViMTIzXHViMjk0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHViYzI5XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCwgXHVhYzAxIFx1ZDFhMFx1YjA3Y1x1YWMwMCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHViYTM5XHVjNzQwIFx1YjUzOFx1YWUzMFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzExXHVhY2ZjIFx1Y2VmNVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMTMxXHViMGU1XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNDA4NmQ5YjItNTllZS00ZGE5LWIyMTQtZTg0Y2M3NzQyNjZlXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0OTRweDsgaGVpZ2h0OiAxNDNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWQxYTBcdWIwN2NcdWFjMDAgMTFcdWI5YzhcdWI5YWMgXHVjNzg4XHViMmU0XHVhY2UwXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI3ZmMgTiA9IDExXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjNzc0XHViNTRjLCBLXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YmE3NCBLID0gM1x1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjZDFkIFx1YjEyNCBcdWFjMWNcdWM3NTggXHViZTE0XHViODVkXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOSBcdWJlMTRcdWI4NWRcdWM1ZDBcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzExXHVjNzc0IDJcdWFjMWNcdWI5Y2MgXHVjNzg4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViNTM4XHVhZTMwXHViOTdjIDZcdWFjMWMgXHVjMGFjXHVjNjU0XHVhY2UwLCA1XHViYzg4IFx1ZDFhMFx1YjA3Y1x1YmQ4MFx1ZDEzMCBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOTAwXHViMmU0XHViYTc0LCBcdWMxMzFcdWIwZTVcdWFjMTFcdWFjZmMgXHVjZWY1XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYTFmMmU3NTQtZjg3MC00MmQ2LWFiZTEtZTUxMzcxMzhjMTJkXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0OTRweDsgaGVpZ2h0OiAxNDRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkMWEwXHViMDdjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgTVx1Yzc3Y1x1YjNkOVx1YzU0OCBcdWFkNmNcdWI5ZTRcdWQ1NWMgXHViNTM4XHVhZTMwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWQxYTBcdWIwN2NcdWM1ZDBcdWFjOGMgXHVjOTAwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWRmOFx1YjBhMCBcdWMxMzFcdWIwZTVcdWM3NDQgXHViMTIzXHVjNzQwIFx1YzEzMVx1YjBlNVx1YWMxMVx1YWNmYyBcdWNlZjVcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzEzMVx1YjBlNVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOLCBNICZsZTsgMTAwMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjBhMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZDZjXHViOWU0XHVkNTVjIFx1YjUzOFx1YWUzMFx1Yzc1OCBcdWMyMTggU1x1YzY0MCBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOGZjXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWQxYTBcdWIwN2NcdWM3NTggXHViYzg4XHVkNjM4IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEgJmxlOyBOLCAxICZsZTsgQStTJm5kYXNoOzEgJmxlOyBOKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWNkMWQgTVx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4ga1x1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQga1x1YmM4OFx1YzlmOCBcdWIwYTBcdWM1ZDAgXHVjMTMxXHViMGU1XHVjNzQ0IFx1YjEyM1x1Yzc0MCBcdWMxMzFcdWIwZTVcdWFjMTFcdWFjZmMgXHVjZWY1XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyAxXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWQxYTBcdWIwN2NcdWFjMDAgMTFcdWI5YzhcdWI5YWMgXHVjNzg4XHVhY2UwLCBcdWJlMTRcdWI4NWRcdWM3NzQgNFx1YWMxY1x1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuIChcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMCk8XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YjBhMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViNTM4XHVhZTMwXHViOTdjIFx1YzhmY1x1YjI5NCBcdWQxYTBcdWIwN2NcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDVcdWJjODhcdWJkODBcdWQxMzAgMTBcdWJjODhcdWM3NzRcdWIyZTQuIFx1YzEzMVx1YjBlNVx1YWMxMSA1LDYsMTBcdWJjODhcdWM1ZDBcdWIyOTQgXHVjMTMxXHViMGU1XHVjNzQ0IFx1YjEyM1x1Yzc0NCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjZWY1XHVjNWQwIFx1YzEzMVx1YjBlNVx1YWMxMVx1Yzc0NCBcdWIxMjNcdWIyOTRcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWIwYTBcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM2ZDBcdWI3OTggXHVjMTMxXHViMGU1XHVjNzc0IFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWFjMTFcdWFjZmMgXHVjZWY1XHVjNzQwIFx1YzVjNlx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzgxNVx1YjJmNVx1Yzc0MCA0XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YjBhMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCAzXHViYzg4XHVkMWEwXHViMDdjXHVjNWQwXHVhYzhjIFx1YjUzOFx1YWUzMFx1Yjk3YyBcdWM5MDBcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjZWY1XHVjNWQwIFx1YzEzMVx1YjBlNVx1Yzc0NCBcdWIxMjNcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHViMGEwXHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWQxYTBcdWIwN2NcdWM1ZDBcdWFjOGMgXHViNTM4XHVhZTMwXHViOTdjIFx1YzkwMFx1YjJlNC4gXHVjNzc0XHViN2YwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjZWY1XHVjNWQwIFx1YzEzMVx1YjBlNVx1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHViMTIzXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4MTVcdWIyZjVcdWM3NDAgNlx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTQzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSkFHT0RBIiwiZGVzY3JpcHRpb24iOiI8cD5TbGF2a28gaGFzIE4gcmFiYml0cyB0aGF0IGhlIGZlZWRzIGV2ZXJ5IGRheSB3aXRoIHZhcmlvdXMgZnJ1aXRzIGFuZCB2ZWdldGFibGVzLiBSYWJiaXRzLCBob3dldmVyLCBwcmVmZXIgc3RyYXdiZXJyaWVzIGFib3ZlIGFsbCBlbHNlLiBTdHJhd2JlcnJpZXMgYXJlIGhhcmQgdG8gZmluZCBhbmQgZXhwZW5zaXZlIGluIHRoZSBtaWRkbGUgb2Ygd2ludGVyLCBzbyBTbGF2a28gb25seSBnaXZlcyBzdHJhd2JlcnJpZXMgdG8gcGFydCBvZiBoaXMgcmFiYml0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2xhdmtvIG51bWJlcmVkIHRoZSByYWJiaXRzIDEgdGhyb3VnaCBOLiBUbyBoZWxwIGtlZXAgdHJhY2sgb2YgaG93IG1hbnkgc3RyYXdiZXJyaWVzIGVhY2ggb2YgdGhlIHJhYmJpdHMgZ290LCBTbGF2a28gZGVjaWRlZCBvbiB0aGUgZm9sbG93aW5nIHN0cmF3YmVycnkgYWxsb2NhdGlvbiBwcm9jZWR1cmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IGRheSBTbGF2a28gcHVyY2hhc2VzIHNvbWUgbnVtYmVyIFMgb2Ygc3RyYXdiZXJyaWVzIGFuZCBjaG9vc2VzIHNvbWUgcmFiYml0IEEgdG8gZ2V0IHRoZSBmaXJzdCBzdHJhd2JlcnJ5LiBSYWJiaXQgQSsxIHdpbGwgZ2V0IHRoZSBzZWNvbmQgc3RyYXdiZXJyeSwgcmFiYml0IEErMiB0aGUgdGhpcmQgZXRjLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FdmVyeSByYWJiaXQgaXMgYXNzaWduZWQgYW4gaW5pdGlhbGx5IGVtcHR5IG1hdGNoYm94LCB0aGUgTiBtYXRjaGJveGVzIGZvcm1pbmcgYSBzaW5nbGUgcm93LiZuYnNwOzxcL3A+XHJcblxyXG48cD5MZXQgSyBiZSB0aGUgbGFyZ2VzdCBpbnRlZ2VyIHN1Y2ggdGhhdCBLJm1pZGRvdDtLICZsZTsgTi4gRXZlcnkgZ3JvdXAgb2YgSyBtYXRjaGJveGVzIChzdGFydGluZyB3aXRoIHRoZSBmaXJzdCkgd2lsbCBhbHNvIGhhdmUgYSBjdXAgbmV4dCB0byB0aGVtLiBXZSBzYXkgdGhhdCBLIGNvbnNlY3V0aXZlIG1hdGNoYm94ZXMgd2l0aCB0aGVpciBjdXAgZm9ybSBhIGJsb2NrLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZnRlciBnaXZpbmcgdGhlIHJhYmJpdHMgdGhlaXIgc3RyYXdiZXJyaWVzLCBTbGF2a28gd2lsbCBwdXQgYSBzaW5nbGUgbWF0Y2ggaW50byB0aGUgbWF0Y2hib3ggb2YgZXZlcnkgcmFiYml0IHRoYXQgZ290IGEgc3RyYXdiZXJyeSwgdW5sZXNzIGhlIHdvdWxkIGJlIHB1dHRpbmcgYSBtYXRjaCBpbnRvIGFsbCBtYXRjaGJveGVzIGluIGEgYmxvY2suIEluc3RlYWQgb2YgcHV0dGluZyBtYXRjaGVzIGludG8gYWxsIG1hdGNoYm94ZXMgaW4gYSBibG9jaywgaGUgd2lsbCBwdXQgYSBzaW5nbGUgbWF0Y2ggaW4gdGhlIGFwcHJvcHJpYXRlIGN1cC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRvdGFsIG51bWJlciBvZiBzdHJhd2JlcnJpZXMgcmVjZWl2ZWQgYnkgYSByYWJiaXQgY2FuIGJlIGNhbGN1bGF0ZWQgYXMgdGhlIG51bWJlciBvZiBtYXRjaGVzIGluIGl0cyBtYXRjaGJveCBwbHVzIHRoZSBudW1iZXIgb2YgbWF0Y2hlcyBpbiBpdHMgY3VwLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzQwODZkOWIyLTU5ZWUtNGRhOS1iMjE0LWU4NGNjNzc0MjY2ZVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNDk0cHg7IGhlaWdodDogMTQzcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBhc3N1bWUgdGhhdCB0aGVyZSBhcmUgMTEgcmFiYml0cywgdGhhdCBpcyBOPTExLiBUaGUgbnVtYmVyIHRocmVlIGlzIHRoZSBsYXJnZXN0IGludGVnZXIgd2hpY2gsIHdoZW4gc3F1YXJlZCwgZ2l2ZXMgYSByZXN1bHQgb2YgYXQgbW9zdCAxMSwgc28gSz0zLiBUaGVyZSB3aWxsIGJlIGZvdXIgYmxvY2tzLCB0aGUgbGFzdCBvZiB0aGVtIGluY29tcGxldGUgd2l0aCBvbmx5IHR3byBtYXRjaGJveGVzLiBJZiBTbGF2a28gYnV5cyA2IHN0cmF3YmVycmllcyBhbmQgZ2l2ZXMgdGhlIGZpcnN0IG9mIHRoZW0gdG8gcmFiYml0IDUsIHRoZSBzdGF0ZSBpbiB0aGUgY3VwcyBhbmQgbWF0Y2hib3hlcyB3aWxsIGJlOiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2ExZjJlNzU0LWY4NzAtNDJkNi1hYmUxLWU1MTM3MTM4YzEyZFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNDk0cHg7IGhlaWdodDogMTQ0cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHNpbXVsYXRlcyB0aGUgYWJvdmUgcHJvY2VkdXJlLCBrbm93aW5nIHRoZSBudW1iZXIgb2YgcmFiYml0cyBOLCB0aGUgbnVtYmVyIG9mIGRheXMgTSBhbmQgdGhlIG51bWJlcnMgUyBhbmQgQSBmb3IgZWFjaCBvZiB0aGUgTSBkYXlzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXZlcnkgZGF5LCBvdXRwdXQgdGhlIHRvdGFsIG51bWJlciBvZiBtYXRjaGVzIGluIGFsbCBtYXRjaGJveGVzIGFuZCBjdXBzIHRoYXQgU2xhdmtvIGFkZGVkIG1hdGNoZXMgdG8gb24gdGhhdCBkYXkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgTiBhbmQgTSBzZXBhcmF0ZWQgYnkgYSBzcGFjZSAoMSAmbGU7IE4sIE0gJmxlOyAxMDAwMDApLCB0aGUgbnVtYmVyIG9mIHJhYmJpdHMgYW5kIGRheXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBTIGFuZCBBIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBUaGVzZSBudW1iZXJzIG1lYW4gdGhhdCBTbGF2a28gcHVyY2hhc2VkIFMgc3RyYXdiZXJyaWVzIHRoYXQgZGF5IGFuZCB0aGF0IHJhYmJpdCBBIHdpbGwgcmVjZWl2ZSB0aGUgZmlyc3Qgb25lICgxICZsZTsgQSAmbGU7IE4sIDEgJmxlOyBBK1MmbmRhc2g7MSAmbGU7IE4pLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBNIG51bWJlcnMsIGVhY2ggb24gYSBzZXBhcmF0ZSBsaW5lLiBUaGUgay10aCBsaW5lIHNob3VsZCBjb250YWluIHRoZSB0b3RhbCBudW1iZXIgb2YgbWF0Y2hlcyBpbiBhbGwgbWF0Y2hib3hlcyBhbmQgY3VwcyB0aGF0IFNsYXZrbyB1c2VkIG9uIGRheSBrLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgZXhhbXBsZSwgdGhlcmUgYXJlIDExIHJhYmJpdHMgYW5kIG1hdGNoYm94ZXMsIGFuZCBmb3VyIGJsb2NrcywgYXMgc2hvd24gaW4gdGhlIGltYWdlIG9uIHRoZSBwcmV2aW91cyBwYWdlLiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPk9uIHRoZSBmaXJzdCBkYXksIFNsYXZrbyBnaXZlcyBzdHJhd2JlcnJpZXMgdG8gcmFiYml0cyA1IHRocm91Z2ggMTAsIHB1dHRpbmcgbWF0Y2hlcyBpbnRvIG1hdGNoYm94ZXMgNSwgNiBhbmQgMTAsIGFuZCBvbmUgaW50byB0aGUgdGhpcmQgY3VwLiBCZWZvcmUgdGhpcyB0aGVyZSB3ZXJlIG5vIG90aGVyIG1hdGNoZXMgaW4gdGhlIG1hdGNoYm94ZXMgYW5kIGN1cHMgaGUgdXNlZCwgc28gdGhlIG91dHB1dCBpcyBmb3VyLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5PbiB0aGUgc2Vjb25kIGRheSwgU2xhdmtvIGdpdmVzIHN0cmF3YmVycmllcyB0byByYWJiaXRzIDEgdGhyb3VnaCAzLCBwdXR0aW5nIGp1c3Qgb25lIG1hdGNoIGludG8gdGhlIGZpcnN0IGN1cC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+T24gdGhlIHRoaXJkIGRheSwgU2xhdmtvIGdpdmVzIHN0cmF3YmVycmllcyB0byBhbGwgaGlzIHJhYmJpdHMsIHB1dHRpbmcgb25lIG1hdGNoIGludG8gZXZlcnkgY3VwLiBBZnRlciBwdXR0aW5nIHRoZSBmb3VyIG1hdGNoZXMgaW50byBjdXBzLCB0aGVyZSBpcyBhIHRvdGFsIG9mIHNpeCBtYXRjaGVzIGluIHRoZSBjdXBzIGhlIHVzZWQsIHNvIHRoZSBvdXRwdXQgaXMgc2l4LiZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #5 3번