Справедливое деление
Вашему другу исполнилось столько лет, и вы с несколькими другими людьми решили подарить ему копию StarCraft II, ведь кто бы не хотел иметь такую игру?
Вы договорились разделить расходы как можно более справедливо. Поскольку у некоторых из вас больше доступных средств, чем у других, вы также решили, что никто не должен платить больше, чем он может себе позволить. Каждый вклад должен быть кратным 1 центу, то есть никто не может платить дробные части цента.
Каждый записывает максимальную сумму, которую он может внести. Учитывая эти максимальные суммы от каждого, вы делите стоимость подарка как можно более справедливо. Это означает, что вы минимизируете наибольшее отклонение вкладов от (1/n)-ой части общей стоимости. В случае ничьей минимизируйте второе по величине отклонение и так далее. Поскольку наименьшая единица вклада — это 1 цент, может быть более одного возможного разделения стоимости. В этом случае лица с более высоким максимальным вкладом платят больше. Если все еще есть неопределенность, те, кто идут первыми в списке, платят больше.
Поскольку вы купили подарок, ваша задача — выяснить, сколько каждый должен заплатить (включая вас).
Входные данные
На первой строке положительное целое число: количество тестов, не более 100. После этого для каждого теста:
Одна строка с двумя целыми числами p и n: цена подарка в центах (1 ≤ p ≤ 1000000) и количество людей (2 ≤ n ≤ 100), которые вносят вклад в подарок (включая вас).
Одна строка с n целыми числами a_i (1 ≤ a_i ≤ 1000000), где a_i — максимальная сумма, в центах, которую i-й человек в списке может внести.
Выходные данные
Для каждого теста:
Одна строка с n целыми числами: суммы, которые каждый человек должен внести в соответствии со схемой. Если общую стоимость нельзя разделить в соответствии с вышеуказанными правилами, строка должна содержать "IMPOSSIBLE".