Справедливий поділ
Це день народження вашого друга, і ви разом з кількома іншими людьми вирішили подарувати йому копію 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" замість цього.