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

문제

"The Drinking Musicians"는 2034년 그래미 어워즈에서 총 6관왕에 오른 유명한 N인조 밴드이다. 이 밴드의 음악은 엄청난 힘을 가지고 있어서, 사람의 생각을 조절할 수 있다. 대표적인 예로 결혼식에서 이 밴드의 "그 남자가 저기 있어"를 축가로 부르면, 모든 신부가 그 남자를 찾아 결혼식장을 나선다고 한다.

이 밴드의 공연을 보는 것은 쉽지 않다. 밴드는 정시에 도착하지 않으며, 공연장의 위치도 잘 모른다. 또, 공연장에 도착했더라도 길을 자주 잃어서 공연장을 찾지 못한다.

무대에 올라서 공연을 시작했다고 문제가 끝나는 것은 아니다. 각 멤버는 공연 도중에 자주 휴식을 취하러 백스테이지로 사라진다. 하지만 멤버 셋 이상이 동시에 휴식을 취하면, 무대 위의 남아있는 멤버들은 모두 큰 혼란에 빠지게 되고 연주를 더 이상 진행할 수 없다.

콘서트는 총 T분이고, 콘서트 도중에 각 멤버는 적절히 휴식을 가질 것이다. 각 멤버가 가지는 휴식 시간은 미리 알고있다.

이 밴드의 내한공연을 30년만에 성사시킨 상근이는 공연을 성공적으로 마치기 위해서 멤버들이 휴식을 가지는 시간을 계획하려고 한다. 무대 위에서 휴식을 취하러 가는 멤버는 많아야 두 명 이어야 한다. 또, 모든 휴식은 콘서트 도중에 일어나야 한다.

모든 멤버는 단 한 번의 휴식을 가질 수 있다. 각 멤버들이 공연이 시작하고 몇 분이 지나면 휴식을 취하러 가도 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 콘서트의 길이 T와 멤버의 수 N이 주어진다. (1 ≤ T ≤ 5000, 1 ≤ N ≤ 500)

다음 줄에는 각 멤버들이 휴식을 취하는 시간이 공백으로 구분되어서 주어진다.

항상 답이 존재하는 경우만 입력으로 주어진다. 하지만, 답이 유일하지 않을 수도 있다. 

출력

각 멤버가 공연이 시작하고 몇 분이 지난 후에 휴식을 가져야 하는지 출력한다. 입력으로 주어진 순서대로 출력한다.

예제 입력 1

8 3
4 4 4

예제 출력 1

0 2 4

예제 입력 2

10 5
7 5 1 2 3

예제 출력 2

3 3 9 0 0
W3sicHJvYmxlbV9pZCI6IjI5OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYjRcdWQ1NWMgXHVhY2Y1XHVjNWYwIiwiZGVzY3JpcHRpb24iOiI8cD4mcXVvdDtUaGUgRHJpbmtpbmcgTXVzaWNpYW5zJnF1b3Q7XHViMjk0IDIwMzRcdWIxNDQgXHVhZGY4XHViNzk4XHViYmY4IFx1YzViNFx1YzZjY1x1Yzk4OFx1YzVkMFx1YzExYyBcdWNkMWQgNlx1YWQwMFx1YzY1NVx1YzVkMCBcdWM2MjRcdWI5NzggXHVjNzIwXHViYTg1XHVkNTVjIE5cdWM3NzhcdWM4NzAgXHViYzM0XHViNGRjXHVjNzc0XHViMmU0LiBcdWM3NzQgXHViYzM0XHViNGRjXHVjNzU4IFx1Yzc0Y1x1YzU0NVx1Yzc0MCBcdWM1YzRcdWNjYWRcdWIwOWMgXHVkNzk4XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMsIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMwZGRcdWFjMDFcdWM3NDQgXHVjODcwXHVjODA4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjMwMFx1ZDQ1Y1x1YzgwMVx1Yzc3OCBcdWM2MDhcdWI4NWMgXHVhY2IwXHVkNjNjXHVjMmRkXHVjNWQwXHVjMTFjIFx1Yzc3NCBcdWJjMzRcdWI0ZGNcdWM3NTggJnF1b3Q7XHVhZGY4IFx1YjBhOFx1Yzc5MFx1YWMwMCBcdWM4MDBcdWFlMzAgXHVjNzg4XHVjNWI0JnF1b3Q7XHViOTdjIFx1Y2Q5NVx1YWMwMFx1Yjg1YyBcdWJkODBcdWI5NzRcdWJhNzQsIFx1YmFhOFx1YjRlMCBcdWMyZTBcdWJkODBcdWFjMDAgXHVhZGY4IFx1YjBhOFx1Yzc5MFx1Yjk3YyBcdWNjM2VcdWM1NDQgXHVhY2IwXHVkNjNjXHVjMmRkXHVjN2E1XHVjNzQ0IFx1YjA5OFx1YzEyMFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWJjMzRcdWI0ZGNcdWM3NTggXHVhY2Y1XHVjNWYwXHVjNzQ0IFx1YmNmNFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjMjdkXHVjOWMwIFx1YzU0YVx1YjJlNC4gXHViYzM0XHViNGRjXHViMjk0IFx1YzgxNVx1YzJkY1x1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWFjZjVcdWM1ZjBcdWM3YTVcdWM3NTggXHVjNzA0XHVjZTU4XHViM2M0IFx1Yzc5OCBcdWJhYThcdWI5NzhcdWIyZTQuIFx1YjYxMCwgXHVhY2Y1XHVjNWYwXHVjN2E1XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU4OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWFlMzhcdWM3NDQgXHVjNzkwXHVjOGZjIFx1Yzc4M1x1YzViNFx1YzExYyBcdWFjZjVcdWM1ZjBcdWM3YTVcdWM3NDQgXHVjYzNlXHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM0XHViMzAwXHVjNWQwIFx1YzYyY1x1Yjc3Y1x1YzExYyBcdWFjZjVcdWM1ZjBcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0XHVhY2UwIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWIwNWRcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhYzAxIFx1YmE2NFx1YmM4NFx1YjI5NCBcdWFjZjVcdWM1ZjAgXHViM2M0XHVjOTExXHVjNWQwIFx1Yzc5MFx1YzhmYyBcdWQ3MzRcdWMyZGRcdWM3NDQgXHVjZGU4XHVkNTU4XHViN2VjIFx1YmMzMVx1YzJhNFx1ZDE0Y1x1Yzc3NFx1YzljMFx1Yjg1YyBcdWMwYWNcdWI3N2NcdWM5YzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWJhNjRcdWJjODQgXHVjMTRiIFx1Yzc3NFx1YzBjMVx1Yzc3NCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVkNzM0XHVjMmRkXHVjNzQ0IFx1Y2RlOFx1ZDU1OFx1YmE3NCwgXHViYjM0XHViMzAwIFx1YzcwNFx1Yzc1OCBcdWIwYThcdWM1NDRcdWM3ODhcdWIyOTQgXHViYTY0XHViYzg0XHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWQwNzAgXHVkNjNjXHViNzgwXHVjNWQwIFx1YmU2MFx1YzljMFx1YWM4YyBcdWI0MThcdWFjZTAgXHVjNWYwXHVjOGZjXHViOTdjIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHVjOWM0XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2Y1OFx1YzExY1x1ZDJiOFx1YjI5NCBcdWNkMWQgVFx1YmQ4NFx1Yzc3NFx1YWNlMCwgXHVjZjU4XHVjMTFjXHVkMmI4IFx1YjNjNFx1YzkxMVx1YzVkMCBcdWFjMDEgXHViYTY0XHViYzg0XHViMjk0IFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWQ3MzRcdWMyZGRcdWM3NDQgXHVhYzAwXHVjOWM4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YmE2NFx1YmM4NFx1YWMwMCBcdWFjMDBcdWM5YzBcdWIyOTQgXHVkNzM0XHVjMmRkIFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJiZjhcdWI5YWMgXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYzM0XHViNGRjXHVjNzU4IFx1YjBiNFx1ZDU1Y1x1YWNmNVx1YzVmMFx1Yzc0NCAzMFx1YjE0NFx1YjljY1x1YzVkMCBcdWMxMzFcdWMwYWNcdWMyZGNcdWQwYTggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNmNVx1YzVmMFx1Yzc0NCBcdWMxMzFcdWFjZjVcdWM4MDFcdWM3M2NcdWI4NWMgXHViOWM4XHVjZTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWJhNjRcdWJjODRcdWI0ZTRcdWM3NzQgXHVkNzM0XHVjMmRkXHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhY2M0XHVkNjhkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYjM0XHViMzAwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWQ3MzRcdWMyZGRcdWM3NDQgXHVjZGU4XHVkNTU4XHViN2VjIFx1YWMwMFx1YjI5NCBcdWJhNjRcdWJjODRcdWIyOTQgXHViOWNlXHVjNTQ0XHVjNTdjIFx1YjQ1MCBcdWJhODUgXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWJhYThcdWI0ZTAgXHVkNzM0XHVjMmRkXHVjNzQwIFx1Y2Y1OFx1YzExY1x1ZDJiOCBcdWIzYzRcdWM5MTFcdWM1ZDAgXHVjNzdjXHVjNWI0XHViMDk4XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YmE2NFx1YmM4NFx1YjI5NCBcdWIyZTggXHVkNTVjIFx1YmM4OFx1Yzc1OCBcdWQ3MzRcdWMyZGRcdWM3NDQgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWJhNjRcdWJjODRcdWI0ZTRcdWM3NzQgXHVhY2Y1XHVjNWYwXHVjNzc0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCBcdWJhODcgXHViZDg0XHVjNzc0IFx1YzljMFx1YjA5OFx1YmE3NCBcdWQ3MzRcdWMyZGRcdWM3NDQgXHVjZGU4XHVkNTU4XHViN2VjIFx1YWMwMFx1YjNjNCBcdWI0MThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Y1OFx1YzExY1x1ZDJiOFx1Yzc1OCBcdWFlMzhcdWM3NzQgVFx1YzY0MCBcdWJhNjRcdWJjODRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFQgJmxlOyA1MDAwLCAxICZsZTsgTiAmbGU7IDUwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYTY0XHViYzg0XHViNGU0XHVjNzc0IFx1ZDczNFx1YzJkZFx1Yzc0NCBcdWNkZThcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NmRcdWMwYzEgXHViMmY1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWIyZjVcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWJhNjRcdWJjODRcdWFjMDAgXHVhY2Y1XHVjNWYwXHVjNzc0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCBcdWJhODcgXHViZDg0XHVjNzc0IFx1YzljMFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHVkNzM0XHVjMmRkXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjk5NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1VWklDQVJJIiwiZGVzY3JpcHRpb24iOiI8cD4mcXVvdDtUaGUgRHJpbmtpbmcgTXVzaWNpYW5zJnF1b3Q7LCBhIHdpZGVseSBrbm93biBhbmQgcG9wdWxhciBmb2xrIGdyb3VwLCBhcmUgY29taW5nIHRvIHlvdXIgdG93bi4gVGhlIG11c2ljaWFucyBhcmUga25vd24gbm90IG9ubHkgYnkgdGhlaXIgcGxheWluZyBza2lsbHMsIGJ1dCBhbHNvIHRoZWlyIHJvdWdoIGNoYXJhY3Rlci4gVGhleSBuZXZlciBhcnJpdmUgb24gdGltZSwgZG9uJiMzOTt0IGtub3cgd2hpY2ggdG93biB0aGV5JiMzOTtyZSBpbiwgYW5kIGZyZXF1ZW50bHkgaGF2ZSB0cm91YmxlIGZpbmRpbmcgdGhlIHN0YWdlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZGRpdGlvbmFsbHksIGR1cmluZyB0aGUgY29uY2VydCwgZWFjaCBvZiB0aGUgbXVzaWNpYW5zIGF0IG9uZSBwb2ludCB0YWtlcyBhIGJyZWFrLiBJZiB0aHJlZSBvciBtb3JlIG9mIHRoZW0gYXJlIG9uIGEgYnJlYWsgYXQgdGhlIHNhbWUgdGltZSwgdGhleSBzdGFydCBzdGlycmluZyB0cm91YmxlIGluIHRvd24gYW5kIHRoZSByZXN0IG9mIHRoZSBncm91cCBzdGFydCBwYW5pY2tpbmcgYW5kIHBsYXlpbmcgdGhlIHdyb25nIGNob3Jkcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNvbmNlcnQgd2lsbCBiZSBUIG1pbnV0ZXMgbG9uZywgZHVyaW5nIHdoaWNoIGVhY2ggb2YgdGhlIE4gbWVtYmVycyB3aWxsIHRha2UgYSBicmVhay4gVGhlIGxlbmd0aCBvZiB0aGUgYnJlYWsgaXMga25vd24gZm9yIGVhY2ggbWVtYmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZWxwIHRoZSBvcmdhbml6ZXIgb2YgdGhlIGNvbmNlcnQgYnkgd3JpdGluZyBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIGhvdyB0byBzY2hlZHVsZSB0aGUgYnJlYWtzIG9mIHRoZSBtZW1iZXIgc28gdGhhdCwgYXQgYW55IGdpdmVuIG1vbWVudCwgYXQgbW9zdCB0d28gYXJlIGFic2VudCBmcm9tIHRoZSBzdGFnZS4gQWxsIGJyZWFrcyBtdXN0IGJlIGVudGlyZWx5IGR1cmluZyB0aGUgY29uY2VydC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBUIGFuZCBOICgxICZsZTsgVCAmbGU7IDUwMDAsIDEgJmxlOyBOICZsZTsgNTAwKSwgdGhlIGxlbmd0aCBvZiB0aGUgY29uY2VydCBpbiBtaW51dGVzIGFuZCB0aGUgbnVtYmVyIG9mIG11c2ljaWFucyBpbiB0aGUgZ3JvdXAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcywgdGhlIGxlbmd0aCBvZiB0aGUgYnJlYWsgaW4gbWludXRlcyBmb3IgZWFjaCBtZW1iZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSBpbnB1dCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IGEgc29sdXRpb24sIGFsdGhvdWdoIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUsIHdpbGwgYWx3YXlzIGV4aXN0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIG11c2ljaWFuIG91dHB1dCBvbmUgaW50ZWdlciwgdGhlIG51bWJlciBvZiBtaW51dGVzIHRoZSBtdXNpY2lhbiB3aWxsIHNwZW5kIG9uIHN0YWdlIGJlZm9yZSBnb2luZyBvbiB0aGUgYnJlYWsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk91dHB1dCB0aGUgbXVzaWNpYW5zIGluIHRoZSBzYW1lIG9yZGVyIHRoZXkgd2VyZSBnaXZlbiBpbiB0aGUgaW5wdXQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #4 4번