시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 78 26 20 39.216%

문제

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

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

10 5
7 5 1 2 3

예제 출력 1

3 3 9 0 0
W3sicHJvYmxlbV9pZCI6IjI5OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYjRcdWQ1NWMgXHVhY2Y1XHVjNWYwIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0JnF1b3Q7VGhlIERyaW5raW5nIE11c2ljaWFucyZxdW90O1x1YjI5NCAyMDM0XHViMTQ0IFx1YWRmOFx1Yjc5OFx1YmJmOCBcdWM1YjRcdWM2Y2NcdWM5ODhcdWM1ZDBcdWMxMWMgXHVjZDFkIDZcdWFkMDBcdWM2NTVcdWM1ZDAgXHVjNjI0XHViOTc4IFx1YzcyMFx1YmE4NVx1ZDU1YyBOXHVjNzc4XHVjODcwIFx1YmMzNFx1YjRkY1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YmMzNFx1YjRkY1x1Yzc1OCBcdWM3NGNcdWM1NDVcdWM3NDAgXHVjNWM0XHVjY2FkXHViMDljIFx1ZDc5OFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMGRkXHVhYzAxXHVjNzQ0IFx1Yzg3MFx1YzgwOFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIzMDBcdWQ0NWNcdWM4MDFcdWM3NzggXHVjNjA4XHViODVjIFx1YWNiMFx1ZDYzY1x1YzJkZFx1YzVkMFx1YzExYyBcdWM3NzQgXHViYzM0XHViNGRjXHVjNzU4ICZxdW90O1x1YWRmOCBcdWIwYThcdWM3OTBcdWFjMDAgXHVjODAwXHVhZTMwIFx1Yzc4OFx1YzViNCZxdW90O1x1Yjk3YyBcdWNkOTVcdWFjMDBcdWI4NWMgXHViZDgwXHViOTc0XHViYTc0LCBcdWJhYThcdWI0ZTAgXHVjMmUwXHViZDgwXHVhYzAwIFx1YWRmOCBcdWIwYThcdWM3OTBcdWI5N2MgXHVjYzNlXHVjNTQ0IFx1YWNiMFx1ZDYzY1x1YzJkZFx1YzdhNVx1Yzc0NCBcdWIwOThcdWMxMjBcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHViYzM0XHViNGRjXHVjNzU4IFx1YWNmNVx1YzVmMFx1Yzc0NCBcdWJjZjRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzI3ZFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YmMzNFx1YjRkY1x1YjI5NCBcdWM4MTVcdWMyZGNcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVhY2Y1XHVjNWYwXHVjN2E1XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjNjNCBcdWM3OTggXHViYWE4XHViOTc4XHViMmU0LiBcdWI2MTAsIFx1YWNmNVx1YzVmMFx1YzdhNVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWIzNTRcdWI3N2NcdWIzYzQgXHVhZTM4XHVjNzQ0IFx1Yzc5MFx1YzhmYyBcdWM3ODNcdWM1YjRcdWMxMWMgXHVhY2Y1XHVjNWYwXHVjN2E1XHVjNzQ0IFx1Y2MzZVx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmIzNFx1YjMwMFx1YzVkMCBcdWM2MmNcdWI3N2NcdWMxMWMgXHVhY2Y1XHVjNWYwXHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNFx1YWNlMCBcdWJiMzhcdWM4MWNcdWFjMDAgXHViMDVkXHViMDk4XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YWMwMSBcdWJhNjRcdWJjODRcdWIyOTQgXHVhY2Y1XHVjNWYwIFx1YjNjNFx1YzkxMVx1YzVkMCBcdWM3OTBcdWM4ZmMgXHVkNzM0XHVjMmRkXHVjNzQ0IFx1Y2RlOFx1ZDU1OFx1YjdlYyBcdWJjMzFcdWMyYTRcdWQxNGNcdWM3NzRcdWM5YzBcdWI4NWMgXHVjMGFjXHViNzdjXHVjOWM0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViYTY0XHViYzg0IFx1YzE0YiBcdWM3NzRcdWMwYzFcdWM3NzQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1ZDczNFx1YzJkZFx1Yzc0NCBcdWNkZThcdWQ1NThcdWJhNzQsIFx1YmIzNFx1YjMwMCBcdWM3MDRcdWM3NTggXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YmE2NFx1YmM4NFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVkMDcwIFx1ZDYzY1x1Yjc4MFx1YzVkMCBcdWJlNjBcdWM5YzBcdWFjOGMgXHViNDE4XHVhY2UwIFx1YzVmMFx1YzhmY1x1Yjk3YyBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YzljNFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNmNThcdWMxMWNcdWQyYjhcdWIyOTQgXHVjZDFkIFRcdWJkODRcdWM3NzRcdWFjZTAsIFx1Y2Y1OFx1YzExY1x1ZDJiOCBcdWIzYzRcdWM5MTFcdWM1ZDAgXHVhYzAxIFx1YmE2NFx1YmM4NFx1YjI5NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVkNzM0XHVjMmRkXHVjNzQ0IFx1YWMwMFx1YzljOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWJhNjRcdWJjODRcdWFjMDAgXHVhYzAwXHVjOWMwXHViMjk0IFx1ZDczNFx1YzJkZCBcdWMyZGNcdWFjMDRcdWM3NDAgXHViYmY4XHViOWFjIFx1YzU0Y1x1YWNlMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0IFx1YmMzNFx1YjRkY1x1Yzc1OCBcdWIwYjRcdWQ1NWNcdWFjZjVcdWM1ZjBcdWM3NDQgMzBcdWIxNDRcdWI5Y2NcdWM1ZDAgXHVjMTMxXHVjMGFjXHVjMmRjXHVkMGE4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjZjVcdWM1ZjBcdWM3NDQgXHVjMTMxXHVhY2Y1XHVjODAxXHVjNzNjXHViODVjIFx1YjljOFx1Y2U1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViYTY0XHViYzg0XHViNGU0XHVjNzc0IFx1ZDczNFx1YzJkZFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWNjNFx1ZDY4ZFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmIzNFx1YjMwMCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVkNzM0XHVjMmRkXHVjNzQ0IFx1Y2RlOFx1ZDU1OFx1YjdlYyBcdWFjMDBcdWIyOTQgXHViYTY0XHViYzg0XHViMjk0IFx1YjljZVx1YzU0NFx1YzU3YyBcdWI0NTAgXHViYTg1IFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHViYWE4XHViNGUwIFx1ZDczNFx1YzJkZFx1Yzc0MCBcdWNmNThcdWMxMWNcdWQyYjggXHViM2M0XHVjOTExXHVjNWQwIFx1Yzc3Y1x1YzViNFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmFhOFx1YjRlMCBcdWJhNjRcdWJjODRcdWIyOTQgXHViMmU4IFx1ZDU1YyBcdWJjODhcdWM3NTggXHVkNzM0XHVjMmRkXHVjNzQ0IFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViYTY0XHViYzg0XHViNGU0XHVjNzc0IFx1YWNmNVx1YzVmMFx1Yzc3NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjZTAgXHViYTg3IFx1YmQ4NFx1Yzc3NCBcdWM5YzBcdWIwOThcdWJhNzQgXHVkNzM0XHVjMmRkXHVjNzQ0IFx1Y2RlOFx1ZDU1OFx1YjdlYyBcdWFjMDBcdWIzYzQgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZjU4XHVjMTFjXHVkMmI4XHVjNzU4IFx1YWUzOFx1Yzc3NCBUXHVjNjQwIFx1YmE2NFx1YmM4NFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgVCAmbGU7IDUwMDAsIDEgJmxlOyBOICZsZTsgNTAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJhNjRcdWJjODRcdWI0ZTRcdWM3NzQgXHVkNzM0XHVjMmRkXHVjNzQ0IFx1Y2RlOFx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YjJmNVx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1YmE2NFx1YmM4NFx1YWMwMCBcdWFjZjVcdWM1ZjBcdWM3NzQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhY2UwIFx1YmE4NyBcdWJkODRcdWM3NzQgXHVjOWMwXHViMDljIFx1ZDZjNFx1YzVkMCBcdWQ3MzRcdWMyZGRcdWM3NDQgXHVhYzAwXHVjODM4XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTk0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTVVaSUNBUkkiLCJkZXNjcmlwdGlvbiI6IjxwPiZxdW90O1RoZSBEcmlua2luZyBNdXNpY2lhbnMmcXVvdDssIGEgd2lkZWx5IGtub3duIGFuZCBwb3B1bGFyIGZvbGsgZ3JvdXAsIGFyZSBjb21pbmcgdG8geW91ciB0b3duLiBUaGUgbXVzaWNpYW5zIGFyZSBrbm93biBub3Qgb25seSBieSB0aGVpciBwbGF5aW5nIHNraWxscywgYnV0IGFsc28gdGhlaXIgcm91Z2ggY2hhcmFjdGVyLiBUaGV5IG5ldmVyIGFycml2ZSBvbiB0aW1lLCBkb24mIzM5O3Qga25vdyB3aGljaCB0b3duIHRoZXkmIzM5O3JlIGluLCBhbmQgZnJlcXVlbnRseSBoYXZlIHRyb3VibGUgZmluZGluZyB0aGUgc3RhZ2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFkZGl0aW9uYWxseSwgZHVyaW5nIHRoZSBjb25jZXJ0LCBlYWNoIG9mIHRoZSBtdXNpY2lhbnMgYXQgb25lIHBvaW50IHRha2VzIGEgYnJlYWsuIElmIHRocmVlIG9yIG1vcmUgb2YgdGhlbSBhcmUgb24gYSBicmVhayBhdCB0aGUgc2FtZSB0aW1lLCB0aGV5IHN0YXJ0IHN0aXJyaW5nIHRyb3VibGUgaW4gdG93biBhbmQgdGhlIHJlc3Qgb2YgdGhlIGdyb3VwIHN0YXJ0IHBhbmlja2luZyBhbmQgcGxheWluZyB0aGUgd3JvbmcgY2hvcmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY29uY2VydCB3aWxsIGJlIFQgbWludXRlcyBsb25nLCBkdXJpbmcgd2hpY2ggZWFjaCBvZiB0aGUgTiBtZW1iZXJzIHdpbGwgdGFrZSBhIGJyZWFrLiBUaGUgbGVuZ3RoIG9mIHRoZSBicmVhayBpcyBrbm93biBmb3IgZWFjaCBtZW1iZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgdGhlIG9yZ2FuaXplciBvZiB0aGUgY29uY2VydCBieSB3cml0aW5nIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgaG93IHRvIHNjaGVkdWxlIHRoZSBicmVha3Mgb2YgdGhlIG1lbWJlciBzbyB0aGF0LCBhdCBhbnkgZ2l2ZW4gbW9tZW50LCBhdCBtb3N0IHR3byBhcmUgYWJzZW50IGZyb20gdGhlIHN0YWdlLiBBbGwgYnJlYWtzIG11c3QgYmUgZW50aXJlbHkgZHVyaW5nIHRoZSBjb25jZXJ0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXJzIFQgYW5kIE4gKDEgJmxlOyBUICZsZTsgNTAwMCwgMSAmbGU7IE4gJmxlOyA1MDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBjb25jZXJ0IGluIG1pbnV0ZXMgYW5kIHRoZSBudW1iZXIgb2YgbXVzaWNpYW5zIGluIHRoZSBncm91cC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgbGluZSBjb250YWlucyBOIGludGVnZXJzIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCB0aGUgbGVuZ3RoIG9mIHRoZSBicmVhayBpbiBtaW51dGVzIGZvciBlYWNoIG1lbWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIGlucHV0IGRhdGEgd2lsbCBiZSBzdWNoIHRoYXQgYSBzb2x1dGlvbiwgYWx0aG91Z2ggbm90IG5lY2Vzc2FyaWx5IHVuaXF1ZSwgd2lsbCBhbHdheXMgZXhpc3QuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbXVzaWNpYW4gb3V0cHV0IG9uZSBpbnRlZ2VyLCB0aGUgbnVtYmVyIG9mIG1pbnV0ZXMgdGhlIG11c2ljaWFuIHdpbGwgc3BlbmQgb24gc3RhZ2UgYmVmb3JlIGdvaW5nIG9uIHRoZSBicmVhay4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T3V0cHV0IHRoZSBtdXNpY2lhbnMgaW4gdGhlIHNhbWUgb3JkZXIgdGhleSB3ZXJlIGdpdmVuIGluIHRoZSBpbnB1dC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=