시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 7 4 25.000%

문제

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

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력

10 5
7 5 1 2 3

예제 출력

3 3 9 0 0

힌트