Greedy Scheduler

Interview

Time limit1sMemory limit1024 MB

Summary

Assign each customer to the cashier who becomes free first, breaking ties by the smaller cashier number, and print that cashier's number for each customer.

Level: Medium4 of 10
Topics: Heap, Greedy, Simulation
Solved: No attempts yet

Problem

A store has $n$ cashiers numbered from 1 to $n$ , and $c$ customers are waiting in a queue. The customer at the front of the queue is always assigned to the first unoccupied cashier, meaning the one with the smallest number. The $i$ th customer's shopping cart takes $t_i$ seconds to process.

For each customer, find which cashier processes their cart.

Input

The first line contains a single integer $m$ , the number of datasets. Each dataset has two lines. The first line contains two space-separated integers $n$ and $c$ ( $1 \le n \le c \le 1000$ ). The second line contains $c$ space-separated integers $t_1, \dots, t_c$ .

Output

For each dataset, print on a single line $c$ integers separated by single spaces. Each integer is the number of the cashier that handles that customer.

Examples1

Example 1

Input

1
3 10
406 424 87 888 871 915 516 81 275 578

Expected output

1 2 3 3 1 2 3 1 2 1