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

문제

오늘은 선영이의 생일이다. 선영이의 친구들은 선영이에게 생일선물로 스타크래프트 2를 사주기로 했다.

선영이의 친구들은 비용을 공정하게 내기로 결정했다. 친구들 중 일부는 다른 친구들보다 돈이 많기 때문에, 각자 낼 수 있는 금액보다 더 많은 금액은 내지 않기로 했다. 모든 사람이 내는 돈은 1원의 배수이다. 즉, 분수로 낼 수는 없다.

친구들은 자신이 낼 수 있는 최대 금액을 적어서 냈다. 이제 이 정보를 이용해서 각자 낼 금액이 얼마인지 계산해보려고 한다.

공정하게 선물 비용을 내려면, 선물 금액의 1/n과 각 사람이 낸 금액의 차이의 최댓값을 최소로 해야 한다. 만약, 같은 경우가 나오는 경우에는 두 번째 차이의 최댓값을 최소로 해야 하고, 이런 식이다. 각 사람이 낼 수 있는 최소 금액은 1원이기 때문에, 금액을 분배하는 방법이 여러 가지가 나올 수 있다. 이 경우에는 돈을 많이 낼 수 있는 사람이 더 내게 된다. 그래도 여러 가지라면, 리스트의 앞에 있는 사람이 돈을 더 낸다.

선영이의 친구들이 낼 수 있는 금액과 선물의 금액이 주어졌을 때, 각자 얼마를 내야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 선물의 가격 p (1 ≤ p ≤ 1,000,000)와 선영이 친구의 수 n (2 ≤ n ≤ 100) 이 주어진다. 둘째 줄에는 각 사람이 낼 수 있는 금액 ai (1 ≤ ai ≤ 1,000,000) 가 주어진다.

출력

각 테스트 케이스마다 각 사람이 내야 하는 금액을 출력한다. 만약, 공정하게 선물을 사는 방법이 없다면 IMPOSSIBLE을 출력한다.

예제 입력 1

3
20 4
10 10 4 4
7 3
1 1 4
34 5
9 8 9 9 4

예제 출력 1

6 6 4 4
IMPOSSIBLE
8 7 8 7 4
W3sicHJvYmxlbV9pZCI6IjM2NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwZGRcdWM3N2MgXHVjMTIwXHViYjNjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1YzBkZFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc0MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMGRkXHVjNzdjXHVjMTIwXHViYjNjXHViODVjIFx1YzJhNFx1ZDBjMFx1ZDA2Y1x1Yjc5OFx1ZDUwNFx1ZDJiOCAyXHViOTdjIFx1YzBhY1x1YzhmY1x1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YWNmNVx1YzgxNVx1ZDU1OFx1YWM4YyBcdWIwYjRcdWFlMzBcdWI4NWMgXHVhY2IwXHVjODE1XHVkNTg4XHViMmU0LiBcdWNlNWNcdWFkNmNcdWI0ZTQgXHVjOTExIFx1Yzc3Y1x1YmQ4MFx1YjI5NCBcdWIyZTRcdWI5NzggXHVjZTVjXHVhZDZjXHViNGU0XHViY2Y0XHViMmU0IFx1YjNjOFx1Yzc3NCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFjMDFcdWM3OTAgXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTA4XHVjNTYxXHViY2Y0XHViMmU0IFx1YjM1NCBcdWI5Y2VcdWM3NDAgXHVhZTA4XHVjNTYxXHVjNzQwIFx1YjBiNFx1YzljMCBcdWM1NGFcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YjBiNFx1YjI5NCBcdWIzYzhcdWM3NDAgMVx1YzZkMFx1Yzc1OCBcdWJjMzBcdWMyMThcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHViZDg0XHVjMjE4XHViODVjIFx1YjBiYyBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFlMDhcdWM1NjFcdWM3NDQgXHVjODAxXHVjNWI0XHVjMTFjIFx1YjBjOFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1Yzc3NCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YWMwMVx1Yzc5MCBcdWIwYmMgXHVhZTA4XHVjNTYxXHVjNzc0IFx1YzViY1x1YjljOFx1Yzc3OFx1YzljMCBcdWFjYzRcdWMwYjBcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZjVcdWM4MTVcdWQ1NThcdWFjOGMgXHVjMTIwXHViYjNjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWIwYjRcdWI4MjRcdWJhNzQsIFx1YzEyMFx1YmIzYyBcdWFlMDhcdWM1NjFcdWM3NTggMVwvblx1YWNmYyBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzc0IFx1YjBiOCBcdWFlMDhcdWM1NjFcdWM3NTggXHVjYzI4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWM3NzRcdWI3ZjAgXHVjMmRkXHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzc0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWFlMDhcdWM1NjFcdWM3NDAgMVx1YzZkMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWUwOFx1YzU2MVx1Yzc0NCBcdWJkODRcdWJjMzBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViM2M4XHVjNzQ0IFx1YjljZVx1Yzc3NCBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViMzU0IFx1YjBiNFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YjNjNCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM3NTggXHVjNTVlXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViM2M4XHVjNzQ0IFx1YjM1NCBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTA4XHVjNTYxXHVhY2ZjIFx1YzEyMFx1YmIzY1x1Yzc1OCBcdWFlMDhcdWM1NjFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAxXHVjNzkwIFx1YzViY1x1YjljOFx1Yjk3YyBcdWIwYjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTIwXHViYjNjXHVjNzU4IFx1YWMwMFx1YWNhOSBwICgxICZsZTsgcCAmbGU7IDEsMDAwLDAwMClcdWM2NDAgXHVjMTIwXHVjNjAxXHVjNzc0IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWMyMTggbiAoMiAmbGU7IG4gJmxlOyAxMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFlMDhcdWM1NjEgYTxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzc0IFx1YjBiNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZTA4XHVjNTYxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjZjVcdWM4MTVcdWQ1NThcdWFjOGMgXHVjMTIwXHViYjNjXHVjNzQ0IFx1YzBhY1x1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IElNUE9TU0lCTEVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM2NjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGYWlyIERpdmlzaW9uIiwiZGVzY3JpcHRpb24iOiI8cD5JdCZyc3F1bztzIHlvdXIgZnJpZW5kJnJzcXVvO3MgYmlydGhkYXksIGFuZCB5b3UgYW5kIHNvbWUgb3RoZXIgcGVvcGxlIGRlY2lkZWQgdG8gYnV5IGhpbSBhIGNvcHkgb2YgU3RhckNyYWZ0IElJLCBiZWNhdXNlIHdobyB3b3VsZG4mcnNxdW87dCB3YW50IHRvIGhhdmUgdGhhdD88XC9wPlxyXG5cclxuPHA+WW91IGFncmVlZCB0byBkaXZpZGUgdGhlIGNvc3RzIGFzIGZhaXJseSBhcyBwb3NzaWJsZS4gU2luY2Ugc29tZSBvZiB5b3UgaGF2ZSBtb3JlIG1vbmV5IGF2YWlsYWJsZSB0aGFuIG90aGVycywgeW91IGFsc28gYWdyZWVkIHRoYXQgbm9ib2R5IGhhcyB0byBwYXkgbW9yZSB0aGFuIGhlIGNhbiBhZmZvcmQuIEV2ZXJ5IGNvbnRyaWJ1dGlvbiB3aWxsIGJlIGEgbXVsdGlwbGUgb2YgMSBjZW50LCBpLmUuLCBub2JvZHkgY2FuIHBheSBmcmFjdGlvbnMgb2YgYSBjZW50LjxcL3A+XHJcblxyXG48cD5FdmVyeWJvZHkgd3JpdGVzIGRvd24gdGhlIG1heGltdW0gYW1vdW50IGhlIGlzIGFibGUgdG8gY29udHJpYnV0ZS4gVGFraW5nIGludG8gYWNjb3VudCB0aGVzZSBtYXhpbXVtIGFtb3VudHMgZnJvbSBldmVyeWJvZHksIHlvdSBzaGFyZSB0aGUgY29zdCBvZiB0aGUgcHJlc2VudCBhcyBmYWlybHkgYXMgcG9zc2libGUuIFRoYXQgbWVhbnMsIHlvdSBtaW5pbWl6ZSB0aGUgbGFyZ2VzdCBkaXN0YW5jZSBvZiB0aGUgY29udHJpYnV0aW9ucyB0byAxXC9uLXRoIG9mIHRoZSB0b3RhbCBjb3N0LiBJbiBjYXNlIG9mIGEgdGllLCBtaW5pbWl6ZSB0aGUgc2Vjb25kIGxhcmdlc3QgZGlzdGFuY2UsIGFuZCBzbyBvbi4gU2luY2UgdGhlIHNtYWxsZXN0IHVuaXQgb2YgY29udHJpYnV0aW9uIGlzIDEgY2VudCwgdGhlcmUgbWlnaHQgYmUgbW9yZSB0aGFuIG9uZSBwb3NzaWJsZSBkaXZpc2lvbiBvZiB0aGUgY29zdC4gSW4gdGhhdCBjYXNlLCBwZXJzb25zIHdpdGggYSBoaWdoZXIgbWF4aW11bSBhbW91bnQgcGF5IG1vcmUuIElmIHRoZXJlIGlzIHN0aWxsIGFtYmlndWl0eSwgdGhvc2Ugd2hvIGNvbWUgXHVmYjAxcnN0IGluIHRoZSBsaXN0IHBheSBtb3JlLjxcL3A+XHJcblxyXG48cD5TaW5jZSB5b3UgYm91Z2h0IHRoZSBwcmVzZW50LCBpdCBpcyB5b3VyIHRhc2sgdG8gXHVmYjAxZ3VyZSBvdXQgaG93IG11Y2ggZXZlcnlib2R5IGhhcyB0byBwYXkgKGluY2x1ZGluZyB5b3UpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIGEgcG9zaXRpdmUgaW50ZWdlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIHAgYW5kIG46IHRoZSBwcmljZSBvZiB0aGUgcHJlc2VudCBpbiBjZW50cyAoMSAmbGU7IHAgJmxlOyAxIDAwMCAwMDApIGFuZCB0aGUgbnVtYmVyIG9mIHBlb3BsZSAoMiAmbGU7IG4gJmxlOyAxMDApIHdobyBjb250cmlidXRlIHRvIHRoZSBwcmVzZW50IChpbmNsdWRpbmcgeW91KS48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBuIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDApLCB3aGVyZSBhaSBpcyB0aGUgbWF4aW11bSBhbW91bnQsIGluIGNlbnRzLCB0aGF0IHRoZSBpLXRoIHBlcnNvbiBvbiB0aGUgbGlzdCBpcyBhYmxlIHRvIGNvbnRyaWJ1dGUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggbiBpbnRlZ2VyczogdGhlIGFtb3VudHMgZWFjaCBwZXJzb24gaGFzIHRvIGNvbnRyaWJ1dGUgYWNjb3JkaW5nIHRvIHRoZSBzY2hlbWUuIElmIHRoZSB0b3RhbCBjb3N0IGNhbm5vdCBiZSBkaXZpZGVkIGFjY29yZGluZyB0byB0aGUgYWJvdmUgcnVsZXMsIHRoZSBsaW5lIG11c3QgY29udGFpbiAmbGRxdW87SU1QT1NTSUJMRSZyZHF1bzsgaW5zdGVhZC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2010 A번