공유 자전거의 이용 균형

문제

한 공유 자전거 보관소는 자전거마다 이용 시간을 기록하여 특정 자전거에 이용이 몰리지 않도록 관리한다. 보관소에는 1번부터 N번까지 서로 다른 번호가 붙은 자전거가 정확히 N대 있다. 각 자전거에는 지금까지 이용한 시간을 모두 더한 누적 이용 시간이 기록되어 있다. 누적 이용 시간의 단위는 분이며, 처음 기록된 값은 자전거마다 다를 수 있다. 관리자는 예약을 입력된 순서대로 한 건씩 처리한다. 예약을 처리할 때에는 현재 누적 이용 시간이 가장 작은 자전거 한 대를 배정한다. 그런 자전거가 여러 대라면 번호가 가장 작은 자전거를 배정한다. 배정한 자전거를 해당 예약의 이용 시간 동안 사용한 것으로 처리한 뒤, 그 자전거의 누적 이용 시간에 예약의 이용 시간을 더한다. 다른 자전거의 기록은 바뀌지 않는다. 이 보관소의 예약은 서로 겹치지 않는다. 각 예약의 이용과 반납이 모두 끝난 다음에 다음 예약을 처리하므로, 모든 예약을 배정하는 순간에는 N대의 자전거가 전부 보관소에 있다. 실제 출발 시각이나 반납 시각은 입력으로 주어지지 않으며, 자전거가 돌아오기를 기다리는 상황도 없다. 따라서 다음 예약에서는 바로 앞 예약에 사용한 자전거를 다시 배정할 수도 있다. 예약의 이용 시간은 자전거를 배정한 뒤 누적 기록을 갱신할 때 사용한다. 배정 기준은 항상 그 예약을 처리하기 직전의 누적 이용 시간이다. 앞으로 들어올 예약의 이용 시간이나 자전거가 앞서 배정된 횟수는 선택 기준에 포함하지 않는다. 누적 이용 시간이 같을 때 사용하는 번호 우선순위도 전체 예약을 처리하는 동안 바뀌지 않는다. 초기 누적 이용 시간과 Q건의 예약 이용 시간이 주어진다. 규칙에 따라 각 예약에 배정되는 자전거 번호를 순서대로 구해야 한다. 예약이 한 건도 없다면 배정 결과가 없다는 뜻으로 EMPTY를 출력한다. 최종 누적 이용 시간은 출력하지 않는다.

입력

첫째 줄에 자전거 수 N과 예약 수 Q가 공백으로 구분되어 주어진다. N은 1 이상 15,000 이하의 정수이고, Q는 0 이상 25,000 이하의 정수다.
둘째 줄에 1번부터 N번 자전거의 초기 누적 이용 시간 A_1, A_2, ..., A_N이 주어진다. 각 A_i는 0 이상 1,000,000 이하의 정수다.
다음 Q개 줄에 예약 이용 시간 T가 하나씩 주어진다. 각 T는 1 이상 1,000,000 이하의 정수다.

출력

각 예약에 배정한 자전거 번호를 예약 순서대로 한 줄에 하나씩 출력한다. Q가 0이면 EMPTY를 한 줄에 출력한다.

3 5
2 2 5
3
1
4
2
1

1
2
2
1
3

1 0
7

EMPTY

2 4
0 0
2
2
1
1

1
2
1
2

출처: Devin.KR 자체 제작