Muzicari

널리 알려진 인기 민속 악단 "술 마시는 악사들"이 여러분의 마을에 온다. 이 악사들은 연주 실력뿐 아니라 거친 성격으로도 유명하다. 이들은 절대 제시간에 도착하지 않고, 자신들이 어느 마을에 있는지도 모르며, 무대를 찾는 데도 자주 애를 먹는다.

또한 공연 중에 악사들은 각자 한 번씩 휴식을 취한다. 셋 이상이 동시에 휴식 중이면 그들은 마을에서 말썽을 부리기 시작하고, 나머지 단원들은 당황해서 엉뚱한 화음을 연주하기 시작한다.

공연은 \(T\)분 동안 진행되며, 그동안 \(N\)명의 단원 각자가 휴식을 취한다. 각 단원의 휴식 시간은 알려져 있다.

어느 순간에도 무대를 비운 사람이 최대 두 명이 되도록 단원들의 휴식 일정을 정하는 프로그램을 작성하여 공연 기획자를 도와주자. 모든 휴식은 공연 시간 안에 완전히 포함되어야 한다.

입력의 첫째 줄에 정수 \(T\)와 \(N\) (\(1 \le T \le 5000\), \(1 \le N \le 500\))이 주어진다. 공연 시간(분)과 악단의 단원 수이다.

다음 줄에 공백 하나로 구분된 정수 \(N\)개가 주어진다. 각 단원의 휴식 시간(분)이다.

참고: 입력 데이터는 해가 항상 존재하도록 주어진다. 단, 해가 유일하지 않을 수도 있다.

각 악사에 대해 정수 하나, 즉 휴식하러 가기 전에 무대에서 보내는 시간(분)을 출력한다.

악사들은 입력에 주어진 것과 같은 순서로 출력한다.

riseoj 작성

출처 COCI 2007/2008 Contest 4