만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

탐욕 스케줄러

면접 대비

시간 제한1초메모리 제한1024 MB

요약
각 손님을 가장 먼저 비는 계산대에 배정하고 같은 시각이면 번호가 작은 계산대를 고르며, 손님마다 처리하는 계산대 번호를 출력합니다.
난이도

보통10점 중 4점

유형
힙, 그리디, 시뮬레이션
정답자
아직 제출이 없습니다

문제

가게에는 1번부터 nn번까지 번호가 붙은 계산대가 nn개 있고, 대기열에는 cc명의 손님이 줄을 서 있습니다. 대기열 맨 앞의 손님은 비어 있는 계산대 중 번호가 가장 작은 곳에 차례로 배정됩니다. ii번째 손님의 장바구니를 처리하는 데 tit_i초가 걸립니다.

각 손님의 장바구니를 어느 계산대가 처리하는지 구하세요.

입력

첫 줄에는 데이터셋의 개수를 나타내는 정수 mm이 주어집니다. 각 데이터셋은 두 줄로 이루어집니다. 첫 줄에는 공백으로 구분된 정수 nn과 cc가 주어집니다(1≤n≤c≤10001 \le n \le c \le 1000). 둘째 줄에는 공백으로 구분된 정수 t1,…,tct_1, \dots, t_c가 주어집니다.

출력

각 데이터셋에 대해 한 줄에 공백으로 구분된 정수 cc개를 출력합니다. 각 정수는 해당 손님을 처리한 계산대의 번호입니다.

예제1

  1. 예제 1

    입력
    1
    3 10
    406 424 87 888 871 915 516 81 275 578
    
    예상 출력
    1 2 3 3 1 2 3 1 2 1