Problem: There are various parking lots such as three-dimensional type and tower type in the city to improve the utilization efficiency of the parking lot. In some parking lots, a "two-stage parking device" as shown in the figure is installed in one parking space to secure a parking space for two cars. This two-stage parking device allows one to be placed on an elevating pallet (a flat iron plate on which a car is placed) and parked in the upper tier, and the other to be parked in the lower tier.

In a parking lot that uses such a two-stage parking device, it is necessary to take out the car parked in the lower tier and dismiss it each time to put in and out the car in the upper tier, so be sure to manage it. Keeps the key to the parked car and puts it in and out as needed.

| <image>
--- | ---

Tsuruga Parking Lot is also one of the parking lots equipped with such a two-stage parking device, but due to lack of manpower, the person who cannot drive the car has become the manager. Therefore, once the car was parked, it could not be moved until the customer returned, and the car in the upper tier could not be put out until the owner of the car in the lower tier returned.

Create a program that meets the rules of the Tsuruga parking lot to help the caretaker who has to handle the cars that come to park one after another.

Tsuruga parking lot facilities

* There is one or more parking spaces, all equipped with a two-stage parking device.
* Each parking space is numbered starting from 1.
* Initially, it is assumed that no car is parked in the parking lot.



Tsuruga parking lot adopts the following rules.

When to stop the car

* The caretaker will be informed of the parking time of the car to be parked.
* We will park first in the parking space where no car is parked.
* If there is no parking space where no car is parked, park in an empty parking space. However, if there are multiple such parking spaces, follow the procedure below to park.
1. If the remaining parking time of a parked car is longer than the parking time of the car you are trying to park, park in the parking space with the smallest difference.
2. If the remaining parking time of any parked car is less than the parking time of the car you are trying to park, park in the parking space with the smallest difference.
* If the car is full (no parking space available), the car you are trying to park will wait in turn until the parking space is available. As soon as it becomes available, we will park in order from the first car we were waiting for.



* Under each condition, if there are multiple applicable parking spaces, the parking space number will be the smallest. In addition, if there are cars leaving at the same time, parking will start after all the cars leaving at the same time, and as long as there are cars waiting, the cars that can be parked will be parked at the same time.

When the car leaves

* Cars that have passed the parking time notified by the manager will be shipped.
* If there are cars in multiple parking spaces that have passed the parking time at the same time, the car with the smallest parking space number will be shipped first.
* If the parking time of the car parked in the upper row has expired, you will have to wait until the car in the lower row leaves the garage. The upper car will be delivered at the same time after the lower car is delivered.



The figure below shows an example of how to park at Tsuruga Parking Lot. In this example, the number of parking spaces is 3, and cars B to E are already parked. Consider that car A, which has a parking time of 70 minutes, arrives there. You cannot park because two cars are already parked in parking space 3, and you will have to park in either parking space 1 or parking space 2 that is still vacant. Car B parked in parking space 1 has 50 minutes remaining and car C parked in parking space 2 has 22 minutes remaining, both of which are less than car A's parking time, so car A's parking Park in parking space 1 where car B, which has a smaller time difference, is parked. As a result, car B, which was parked earlier, will be in the upper row.

<image>


Create a program that inputs the number of parking spaces m, the number of cars parked n, and the parking time t of each car, and outputs the car reference numbers in the order in which they come out of the parking lot. However, cars are assigned an integer reference number starting with 1 in the order of input, and cars will come to park one by one every 10 minutes in the order of the reference number.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:


m n
t1
t2
::
tn


The first line gives the number of two-stage parking devices m (1 ≤ m ≤ 10) and the number of cars parked n (1 ≤ n ≤ 100). The next n lines are given the parking time ti (1 ≤ ti ≤ 120) for the i-th car.

The number of datasets does not exceed 20.

Output

The reference number of the car is output to one line in the order of coming out of the parking lot for each data set. Please output the reference numbers separated by blanks.

Example

Input

3 5
90
52
82
84
70
2 4
10
30
40
60
0 0


Output

2 5 1 4 3
1 2 4 3

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
#include <set>

struct Parking {
	int car_id, out_time;
};
struct Car {
	int id, duration;
};
class Park {
	std::vector<std::vector<Parking>> space;
	bool has_empty_space() const {
		return std::any_of(space.begin(), space.end(), [](const std::vector<Parking>& vec) {return vec.empty(); });
	}
	void push_to_empty_space(int time, Car car) {
		std::find_if(space.begin(), space.end(), [](const std::vector<Parking>& vec) {return vec.empty(); })->push_back(Parking{ car.id, time + car.duration });
	}
	bool has_second_space() const {
		return std::any_of(space.begin(), space.end(), [](const std::vector<Parking>& vec) {return vec.size() == 1; });
	}
	bool has_over_time(int out_time) const {
		return std::any_of(space.begin(), space.end(), [out_time](const std::vector<Parking>& vec) {return vec.size() == 1 && vec.back().out_time >= out_time; });
	}
	void push_to_second_space(int time, Car car) {
		const auto out_time = time + car.duration;
		if (has_over_time(out_time)) {
			auto min = std::min_element(space.begin(), space.end(), [out_time](const std::vector<Parking>& a, const std::vector<Parking>& b) {return ((a.size() != 1 || a.back().out_time < out_time) ? INT_MAX : a.back().out_time) < ((b.size() != 1 || b.back().out_time < out_time) ? INT_MAX : b.back().out_time); });
			min->push_back(Parking{ car.id, out_time });
		}
		else {
			auto max = std::max_element(space.begin(), space.end(), [](const std::vector<Parking>& a, const std::vector<Parking>& b) {return (a.size() != 1 ? INT_MIN : a.back().out_time) < (b.size() != 1 ? INT_MIN : b.back().out_time); });
			max->push_back(Parking{ car.id, out_time });
		}
	}

public:
	Park(int size) : space(size) {};
	int park_count() const {
		return std::accumulate(space.begin(), space.end(), 0, [](int acc, const std::vector<Parking>& vec) {return acc + vec.size(); });
	}
	int next_out() const {
		if (park_count() == 0) return INT_MAX;
		return std::min_element(space.begin(), space.end(), [](const std::vector<Parking>& a, const std::vector<Parking>& b) {return (a.empty() ? INT_MAX : a.back().out_time) < (b.empty() ? INT_MAX : b.back().out_time); })->back().out_time;
	}
	int pop_car() {
		auto min = std::min_element(space.begin(), space.end(), [](const std::vector<Parking>& a, const std::vector<Parking>& b) {return (a.empty() ? INT_MAX : a.back().out_time) < (b.empty() ? INT_MAX : b.back().out_time); });
		const auto result = min->back();
		min->pop_back();
		if (!min->empty()) min->back().out_time = std::max(min->back().out_time, result.out_time);
		return result.car_id;
	}
	bool has_space() const {
		return has_empty_space() || has_second_space();
	}
	void park_car(int time, Car car) {
		if (has_empty_space()) push_to_empty_space(time, car);
		else push_to_second_space(time, car);
	}
};
int main() {
	while (true) {
		int m, n; std::cin >> m >> n; if (m == 0 && n == 0) break;
		std::vector<Car> cars; cars.reserve(n);
		for (auto i = 0; i < n; ++i) {
			int t; std::cin >> t;
			cars.push_back(Car{ i, t });
		}
		Park park(m);
		std::queue<Car> waiting;
		std::vector<int> out_id; out_id.reserve(n);
		for (auto i = 0; i < n; ++i) {
			const int time = i * 10;
			while (park.next_out() <= time) {
				const auto current_time = park.next_out();
				while (park.next_out() == current_time) {
					out_id.push_back(park.pop_car());
				}
				while (park.has_space() && !waiting.empty()) {
					park.park_car(current_time, waiting.front());
					waiting.pop();
				}
			}
			if (park.has_space()) {
				park.park_car(time, cars[i]);
			}
			else {
				waiting.push(cars[i]);
			}
		}
		while (park.park_count() != 0) {
			const auto current_time = park.next_out();
			while (park.next_out() == current_time) {
				out_id.push_back(park.pop_car());
			}
			while (park.has_space() && !waiting.empty()) {
				park.park_car(current_time, waiting.front());
				waiting.pop();
			}
		}
		for (auto i = 0; i < n; ++i) {
			if (i != 0) std::cout << ' ';
			std::cout << out_id[i] + 1;
		}
		std::cout << '\n';
	}
}