시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 18 9 9 60.000%

문제

상근이는 토끼 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

힌트

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

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

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

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

W3sicHJvYmxlbV9pZCI6IjI5NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxYTBcdWIwN2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQxYTBcdWIwN2MgTlx1YjljOFx1YjlhY1x1Yjk3YyBcdWQwYTRcdWM2YjBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWIyOTQgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWQxYTBcdWIwN2NcdWM1ZDBcdWFjOGMgXHViMmU0XHVjNTkxXHVkNTVjIFx1YzU3Y1x1Y2M0NFx1YzY0MCBcdWFjZmNcdWM3N2NcdWM3NDQgXHViYTM5XHVjNzc0XHViODVjIFx1YzhmY1x1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1ZDFhMFx1YjA3Y1x1YjI5NCBcdWI1MzhcdWFlMzBcdWI5N2MgXHVhYzAwXHVjN2E1IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YWNhOFx1YzZiOFx1YzVkMFx1YjI5NCBcdWI1MzhcdWFlMzBcdWI5N2MgXHVhZDZjXHVkNTU4XHVhZTMwXHVhYzAwIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MzVcdWFjZTAsIFx1YWMwMFx1YWNhOVx1YjNjNCBcdWJlNDRcdWMyZjhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzdjXHViZDgwIFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4Y1x1YjljYyBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOGZjXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0IFx1ZDFhMFx1YjA3Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgXHVjMjJiXHVjNzkwXHVjNzc0XHVhY2UwLCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVkMWEwXHViMDdjXHVhYzAwIFx1YmEzOVx1YjI5NCBcdWI1MzhcdWFlMzBcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YWUzMFx1Yjg1ZFx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYzI5XHViYzk1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0XHVjNzdjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI1MzhcdWFlMzAgU1x1YWMxY1x1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YWNlMCBcdWIwOWMgXHViNGE0LCBBXHViYzg4IFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjUzOFx1YWUzMFx1Yjk3YywgQSsxXHViYzg4IFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YjUzOFx1YWUzMFx1Yjk3YywgQSsyXHViYzg4IFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YjUzOFx1YWUzMFx1Yjk3YywuLi4uIFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDFhMFx1YjA3Y1x1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMTMxXHViMGU1XHVhYzExXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWMxMzFcdWIwZTVcdWFjMTFcdWM3NDAgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5LJm1pZGRvdDtLICZsZTsgTlx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBLXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWNjYWIgXHVjMTMxXHViMGU1XHVhYzExXHViZDgwXHVkMTMwIEtcdWFjMWNcdWM1MjkgXHVhZGY4XHViOGY5XHVjNzQ0IFx1YzljMFx1YzViNFx1YzkwMFx1YjJlNC4gXHVhYzAxIFx1YzEzMVx1YjBlNVx1YWMxMVx1Yzc1OCBcdWM1NWVcdWM1ZDBcdWIyOTQgXHVjZWY1XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWIxOTNcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWM1ZjBcdWMxOGRcdWQ1NThcdWIyOTQgS1x1YWMxYyBcdWMxMzFcdWIwZTVcdWFjMTFcdWFjZmMgXHVjZWY1XHVjNzQ0IFx1YmUxNFx1YjdlZFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOTAwIFx1YjJlNFx1Yzc0Y1x1YzVkMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjUzOFx1YWUzMFx1Yjk3YyBcdWJjMWJcdWM3NDAgXHVkMWEwXHViMDdjXHVjNzU4IFx1YzEzMVx1YjBlNVx1YWMxMVx1YzVkMCBcdWMxMzFcdWIwZTVcdWM3NDQgXHViMTIzXHViMjk0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM1YjRcdWI1YTQgXHViZTE0XHViN2VkXHVjNWQwIFx1YmFhOFx1YjRlMCBcdWMxMzFcdWIwZTVcdWFjMTFcdWM1ZDAgXHVjMTMxXHViMGU1XHVjNzQ0IFx1YjEyM1x1YzViNFx1YzU3Y1x1YjQxY1x1YjJlNFx1YmE3NCwgXHVjMTMxXHViMGU1XHVhYzExIFx1YjMwMFx1YzJlMFx1YzVkMCBcdWNlZjVcdWM1ZDAgXHVjMTMxXHViMGU1XHVjNzQ0IFx1YjEyM1x1YjI5NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQsIFx1YWMwMSBcdWQxYTBcdWIwN2NcdWFjMDAgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1YmEzOVx1Yzc0MCBcdWI1MzhcdWFlMzBcdWM3NTggXHVjMjE4XHViMjk0IFx1YzEzMVx1YjBlNVx1YWMxMVx1YWNmYyBcdWNlZjVcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzEzMVx1YjBlNVx1Yzc1OCBcdWMyMThcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RrMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDhweDsgd2lkdGg6NDk2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWQxYTBcdWIwN2NcdWFjMDAgMTFcdWI5YzhcdWI5YWMgXHVjNzg4XHViMmU0XHVhY2UwXHVkNTU4XHVjNzkwLiBcdWFkZjhcdWI3ZmMgTiA9IDExXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgS1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWJhNzQgSyA9IDNcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1Y2QxZCBcdWIxMjQgXHVhYzFjXHVjNzU4IFx1YmUxNFx1YjdlZFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViZTE0XHViN2VkXHVjNWQwXHViMjk0IFx1YzEzMVx1YjBlNVx1YWMxMVx1Yzc3NCAyXHVhYzFjXHViOWNjIFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjUzOFx1YWUzMFx1Yjk3YyA2XHVhYzFjIFx1YzBhY1x1YzY1NFx1YWNlMCwgNVx1YmM4OCBcdWQxYTBcdWIwN2NcdWJkODBcdWQxMzAgXHViNTM4XHVhZTMwXHViOTdjIFx1YzkwMFx1YjJlNFx1YmE3NCwgXHVjMTMxXHViMGU1XHVhYzExXHVhY2ZjIFx1Y2VmNVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMTMxXHViMGU1XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RrMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNTFweDsgd2lkdGg6NTAzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkMWEwXHViMDdjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgTVx1Yzc3Y1x1YjNkOVx1YzU0OCBcdWFkNmNcdWI5ZTRcdWQ1NWMgXHViNTM4XHVhZTMwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWQxYTBcdWIwN2NcdWM1ZDBcdWFjOGMgXHVjOTAwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFkZjhcdWIwYTAgXHVjMTMxXHViMGU1XHVjNzQ0IFx1YjEyM1x1Yzc0MCBcdWMxMzFcdWIwZTVcdWFjMTFcdWFjZmMgXHVjZWY1XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMxMzFcdWIwZTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiwgTSAmbGU7IDEwMDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWIwYTAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWQ2Y1x1YjllNFx1ZDU1YyBcdWI1MzhcdWFlMzBcdWM3NTggXHVjMjE4IFNcdWM2NDAgXHViNTM4XHVhZTMwXHViOTdjIFx1YzhmY1x1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVkMWEwXHViMDdjXHVjNzU4IFx1YmM4OFx1ZDYzOCBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBICZsZTsgTiwgMSAmbGU7IEErUyZuZGFzaDsxICZsZTsgTik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVjZDFkIE1cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIGtcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGtcdWJjODhcdWM5ZjggXHViMGEwXHVjNWQwIFx1YzEzMVx1YjBlNVx1Yzc0NCBcdWIxMjNcdWM3NDAgXHVjMTMxXHViMGU1XHVhYzExXHVhY2ZjIFx1Y2VmNVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMTMxXHViMGU1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1ZDFhMFx1YjA3Y1x1YWMwMCAxMVx1YjljOFx1YjlhYyBcdWM3ODhcdWFjZTAsIFx1YmUxNFx1YjdlZFx1Yzc3NCA0XHVhYzFjXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC4gKFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwKTxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHViMGEwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOGZjXHViMjk0IFx1ZDFhMFx1YjA3Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgNVx1YmM4OFx1YmQ4MFx1ZDEzMCAxMFx1YmM4OFx1Yzc3NFx1YjJlNC4gXHVjMTMxXHViMGU1XHVhYzExIDUsNiwxMFx1YmM4OFx1YzVkMFx1YjI5NCBcdWMxMzFcdWIwZTVcdWM3NDQgXHViMTIzXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWNlZjVcdWM1ZDAgXHVjMTMxXHViMGU1XHVhYzExXHVjNzQ0IFx1YjEyM1x1YjI5NFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YjBhMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzZkMFx1Yjc5OCBcdWMxMzFcdWIwZTVcdWM3NzQgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzEzMVx1YjBlNVx1YWMxMVx1YWNmYyBcdWNlZjVcdWM3NDAgXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjODE1XHViMmY1XHVjNzQwIDRcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHViMGEwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIDNcdWJjODhcdWQxYTBcdWIwN2NcdWM1ZDBcdWFjOGMgXHViNTM4XHVhZTMwXHViOTdjIFx1YzkwMFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNlZjVcdWM1ZDAgXHVjMTMxXHViMGU1XHVjNzQ0IFx1YjEyM1x1YzczY1x1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWIwYTBcdWM1ZDBcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDFhMFx1YjA3Y1x1YzVkMFx1YWM4YyBcdWI1MzhcdWFlMzBcdWI5N2MgXHVjOTAwXHViMmU0LiBcdWM3NzRcdWI3ZjAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWNlZjVcdWM1ZDAgXHVjMTMxXHViMGU1XHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWIxMjNcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzgxNVx1YjJmNVx1Yzc0MCA2XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5NDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKQUdPREEiLCJkZXNjcmlwdGlvbiI6IjxwPlNsYXZrbyBoYXMgTiByYWJiaXRzIHRoYXQgaGUgZmVlZHMgZXZlcnkgZGF5IHdpdGggdmFyaW91cyBmcnVpdHMgYW5kIHZlZ2V0YWJsZXMuIFJhYmJpdHMsIGhvd2V2ZXIsIHByZWZlciBzdHJhd2JlcnJpZXMgYWJvdmUgYWxsIGVsc2UuIFN0cmF3YmVycmllcyBhcmUgaGFyZCB0byBmaW5kIGFuZCBleHBlbnNpdmUgaW4gdGhlIG1pZGRsZSBvZiB3aW50ZXIsIHNvIFNsYXZrbyBvbmx5IGdpdmVzIHN0cmF3YmVycmllcyB0byBwYXJ0IG9mIGhpcyByYWJiaXRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TbGF2a28gbnVtYmVyZWQgdGhlIHJhYmJpdHMgMSB0aHJvdWdoIE4uIFRvIGhlbHAga2VlcCB0cmFjayBvZiBob3cgbWFueSBzdHJhd2JlcnJpZXMgZWFjaCBvZiB0aGUgcmFiYml0cyBnb3QsIFNsYXZrbyBkZWNpZGVkIG9uIHRoZSBmb2xsb3dpbmcgc3RyYXdiZXJyeSBhbGxvY2F0aW9uIHByb2NlZHVyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgZGF5IFNsYXZrbyBwdXJjaGFzZXMgc29tZSBudW1iZXIgUyBvZiBzdHJhd2JlcnJpZXMgYW5kIGNob29zZXMgc29tZSByYWJiaXQgQSB0byBnZXQgdGhlIGZpcnN0IHN0cmF3YmVycnkuIFJhYmJpdCBBKzEgd2lsbCBnZXQgdGhlIHNlY29uZCBzdHJhd2JlcnJ5LCByYWJiaXQgQSsyIHRoZSB0aGlyZCBldGMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IHJhYmJpdCBpcyBhc3NpZ25lZCBhbiBpbml0aWFsbHkgZW1wdHkgbWF0Y2hib3gsIHRoZSBOIG1hdGNoYm94ZXMgZm9ybWluZyBhIHNpbmdsZSByb3cuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkxldCBLIGJlIHRoZSBsYXJnZXN0IGludGVnZXIgc3VjaCB0aGF0IEsmbWlkZG90O0sgJmxlOyBOLiBFdmVyeSBncm91cCBvZiBLIG1hdGNoYm94ZXMgKHN0YXJ0aW5nIHdpdGggdGhlIGZpcnN0KSB3aWxsIGFsc28gaGF2ZSBhIGN1cCBuZXh0IHRvIHRoZW0uIFdlIHNheSB0aGF0IEsgY29uc2VjdXRpdmUgbWF0Y2hib3hlcyB3aXRoIHRoZWlyIGN1cCBmb3JtIGEgYmxvY2suJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIGdpdmluZyB0aGUgcmFiYml0cyB0aGVpciBzdHJhd2JlcnJpZXMsIFNsYXZrbyB3aWxsIHB1dCBhIHNpbmdsZSBtYXRjaCBpbnRvIHRoZSBtYXRjaGJveCBvZiBldmVyeSByYWJiaXQgdGhhdCBnb3QgYSBzdHJhd2JlcnJ5LCB1bmxlc3MgaGUgd291bGQgYmUgcHV0dGluZyBhIG1hdGNoIGludG8gYWxsIG1hdGNoYm94ZXMgaW4gYSBibG9jay4gSW5zdGVhZCBvZiBwdXR0aW5nIG1hdGNoZXMgaW50byBhbGwgbWF0Y2hib3hlcyBpbiBhIGJsb2NrLCBoZSB3aWxsIHB1dCBhIHNpbmdsZSBtYXRjaCBpbiB0aGUgYXBwcm9wcmlhdGUgY3VwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdG90YWwgbnVtYmVyIG9mIHN0cmF3YmVycmllcyByZWNlaXZlZCBieSBhIHJhYmJpdCBjYW4gYmUgY2FsY3VsYXRlZCBhcyB0aGUgbnVtYmVyIG9mIG1hdGNoZXMgaW4gaXRzIG1hdGNoYm94IHBsdXMgdGhlIG51bWJlciBvZiBtYXRjaGVzIGluIGl0cyBjdXAuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGsxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0OHB4OyB3aWR0aDo0OTZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgYXNzdW1lIHRoYXQgdGhlcmUgYXJlIDExIHJhYmJpdHMsIHRoYXQgaXMgTj0xMS4gVGhlIG51bWJlciB0aHJlZSBpcyB0aGUgbGFyZ2VzdCBpbnRlZ2VyIHdoaWNoLCB3aGVuIHNxdWFyZWQsIGdpdmVzIGEgcmVzdWx0IG9mIGF0IG1vc3QgMTEsIHNvIEs9My4gVGhlcmUgd2lsbCBiZSBmb3VyIGJsb2NrcywgdGhlIGxhc3Qgb2YgdGhlbSBpbmNvbXBsZXRlIHdpdGggb25seSB0d28gbWF0Y2hib3hlcy4gSWYgU2xhdmtvIGJ1eXMgNiBzdHJhd2JlcnJpZXMgYW5kIGdpdmVzIHRoZSBmaXJzdCBvZiB0aGVtIHRvIHJhYmJpdCA1LCB0aGUgc3RhdGUgaW4gdGhlIGN1cHMgYW5kIG1hdGNoYm94ZXMgd2lsbCBiZTombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90azIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTUxcHg7IG9wYWNpdHk6MC45OyB3aWR0aDo1MDNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBzaW11bGF0ZXMgdGhlIGFib3ZlIHByb2NlZHVyZSwga25vd2luZyB0aGUgbnVtYmVyIG9mIHJhYmJpdHMgTiwgdGhlIG51bWJlciBvZiBkYXlzIE0gYW5kIHRoZSBudW1iZXJzIFMgYW5kIEEgZm9yIGVhY2ggb2YgdGhlIE0gZGF5cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV2ZXJ5IGRheSwgb3V0cHV0IHRoZSB0b3RhbCBudW1iZXIgb2YgbWF0Y2hlcyBpbiBhbGwgbWF0Y2hib3hlcyBhbmQgY3VwcyB0aGF0IFNsYXZrbyBhZGRlZCBtYXRjaGVzIHRvIG9uIHRoYXQgZGF5LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGludGVnZXJzIE4gYW5kIE0gc2VwYXJhdGVkIGJ5IGEgc3BhY2UgKDEgJmxlOyBOLCBNICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiByYWJiaXRzIGFuZCBkYXlzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgUyBhbmQgQSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlc2UgbnVtYmVycyBtZWFuIHRoYXQgU2xhdmtvIHB1cmNoYXNlZCBTIHN0cmF3YmVycmllcyB0aGF0IGRheSBhbmQgdGhhdCByYWJiaXQgQSB3aWxsIHJlY2VpdmUgdGhlIGZpcnN0IG9uZSAoMSAmbGU7IEEgJmxlOyBOLCAxICZsZTsgQStTJm5kYXNoOzEgJmxlOyBOKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgTSBudW1iZXJzLCBlYWNoIG9uIGEgc2VwYXJhdGUgbGluZS4gVGhlIGstdGggbGluZSBzaG91bGQgY29udGFpbiB0aGUgdG90YWwgbnVtYmVyIG9mIG1hdGNoZXMgaW4gYWxsIG1hdGNoYm94ZXMgYW5kIGN1cHMgdGhhdCBTbGF2a28gdXNlZCBvbiBkYXkgay4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGV4YW1wbGUsIHRoZXJlIGFyZSAxMSByYWJiaXRzIGFuZCBtYXRjaGJveGVzLCBhbmQgZm91ciBibG9ja3MsIGFzIHNob3duIGluIHRoZSBpbWFnZSBvbiB0aGUgcHJldmlvdXMgcGFnZS4mbmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5PbiB0aGUgZmlyc3QgZGF5LCBTbGF2a28gZ2l2ZXMgc3RyYXdiZXJyaWVzIHRvIHJhYmJpdHMgNSB0aHJvdWdoIDEwLCBwdXR0aW5nIG1hdGNoZXMgaW50byBtYXRjaGJveGVzIDUsIDYgYW5kIDEwLCBhbmQgb25lIGludG8gdGhlIHRoaXJkIGN1cC4gQmVmb3JlIHRoaXMgdGhlcmUgd2VyZSBubyBvdGhlciBtYXRjaGVzIGluIHRoZSBtYXRjaGJveGVzIGFuZCBjdXBzIGhlIHVzZWQsIHNvIHRoZSBvdXRwdXQgaXMgZm91ci4mbmJzcDs8XC9saT5cclxuXHQ8bGk+T24gdGhlIHNlY29uZCBkYXksIFNsYXZrbyBnaXZlcyBzdHJhd2JlcnJpZXMgdG8gcmFiYml0cyAxIHRocm91Z2ggMywgcHV0dGluZyBqdXN0IG9uZSBtYXRjaCBpbnRvIHRoZSBmaXJzdCBjdXAuJm5ic3A7PFwvbGk+XHJcblx0PGxpPk9uIHRoZSB0aGlyZCBkYXksIFNsYXZrbyBnaXZlcyBzdHJhd2JlcnJpZXMgdG8gYWxsIGhpcyByYWJiaXRzLCBwdXR0aW5nIG9uZSBtYXRjaCBpbnRvIGV2ZXJ5IGN1cC4gQWZ0ZXIgcHV0dGluZyB0aGUgZm91ciBtYXRjaGVzIGludG8gY3VwcywgdGhlcmUgaXMgYSB0b3RhbCBvZiBzaXggbWF0Y2hlcyBpbiB0aGUgY3VwcyBoZSB1c2VkLCBzbyB0aGUgb3V0cHV0IGlzIHNpeC4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: cheetose