Впервые стартап Поликарпа закончил год с прибылью! Теперь он собирается распределить \(k\) бурлей премии среди \(n\) сотрудников.
Известно, что текущая заработная плата \(i\)-го сотрудника составляет \(a_i\), все значения \(a_i\) в компании — различны.
Поликарп хочет распределить \(k\) бурлей суммарной премии между \(n\) сотрудниками и в этом месяце \(i\)-му из них выплатить не \(a_i\), а \(a_i+d_i\) (\(d_i \ge 0\), \(d_i\) — целое), где \(d_i\) — премиальная часть для \(i\)-го сотрудника. Конечно, \(d_1+d_2+\dots+d_n=k\).
Поликарп руководствуется двумя принципами для выбора значений \(d_i\):
- то, как соотносятся зарплаты между собой, не должно измениться: тот кто получал больше всех (\(a_i\) максимально), и при выплате с премией должен получать больше всех (\(a_i+d_i\) тоже максимально), тот, у кого зарплата была второй по величине, и при выплате с премией должен получать вторую по величине зарплату, и так далее;
- чтобы подчеркнуть, что годовая прибыль — общий результат, Поликарп хочет минимизировать максимальную выплату (то есть минимизировать максимальное значение \(a_i+d_i\)).
Помогите Поликарпу найти такие неотрицательные целые премии \(d_i\), что:
- их сумма равна \(k\);
- для каждого сотрудника количество тех, кто получает больше него, осталось неизменным (то есть, если отсортировать сотрудников по \(a_i\) и по \(a_i+d_i\), то получится одинаковый порядок сотрудников);
- все \(a_i + d_i\) различны;
- максимальное из значений \(a_i+d_i\) — минимально.
Помогите Поликарпу и выведите любой возможных из вариантов \(d_1, d_2, \dots, d_n\).
Выходные данные
Выведите ответы на \(t\) заданных наборов входных данных в порядке их записи в тесте. Ответ выводите в виде последовательности неотрицательных целых чисел \(d_1, d_2, \dots, d_n\). Если ответов несколько, то выведите любой из них.