시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 28 14 14 63.636%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력

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

예제 출력

6 6 4 4
IMPOSSIBLE
8 7 8 7 4

힌트