Справедливий поділ#2449

Справедливий поділ

1 секунда

64 мегабайти

Складна

У твого друга день народження, і ти разом з іншими вирішили подарувати йому копію StarCraft II, адже хто б не хотів мати таку гру?

Ви погодилися поділити витрати якнайсправедливіше. Оскільки хтось із вас має більше грошей, а хтось менше, ви також домовилися, що ніхто не повинен платити більше, ніж може собі дозволити. Кожен внесок буде кратний $1$ центу, тобто ніхто не платитиме частину цента.

Кожен записує максимальну суму, яку може внести. Врахувавши ці максимальні суми, ви розподіляєте вартість подарунка якнайсправедливіше. Це означає, що ви мінімізуєте найбільше відхилення внеску від $1/ n$ всієї суми. Якщо є кілька варіантів, ви мінімізуєте друге за величиною відхилення, і так далі. Оскільки найменша одиниця внеску — $1$ цент, можливий не один розподіл суми. У такому випадку особи з більшим максимальним внеском платять більше. Якщо й після цього виникає неоднозначність, ті, хто стоїть раніше у списку, платять більше.

Оскільки ти купував(-ла) подарунок, твоя задача — визначити, скільки має платити кожен (включаючи себе).

Вхідні дані

Перший рядок містить додатне ціле число: кількість тестових випадків, не більше $100$ . Для кожного тестового випадку:

Один рядок з двома цілими числами $p$ і $n$ : ціна подарунка в центах ( $1 \leq p \leq 1000000$ 1 \leq p \leq 1000000) і кількість людей ( $2 \leq n \leq 100$ 2 \leq n \leq 100), які скидаються на подарунок (включаючи тебе).
Один рядок з $n$ цілих чисел $a_{i}$ a_i ( $1 \leq a_{i} \leq 1000000$ 1 \leq a_i \leq 1000000), де $a_{i}$ a_i — максимальна сума в центах, яку $i$ -та людина зі списку може внести.

Вихідні дані

Для кожного тестового випадку:

Один рядок з $n$ цілих чисел: суми, які кожен має внести згідно зі схемою. Якщо поділити вартість згідно з описаними правилами неможливо, у рядку слід вивести "IMPOSSIBLE".

Приклади

Приклад 1