Зменшення масиву

Вхідні дані

Перший рядок містить три цілі числа $n$, $k$, $t$ (1 \leq n \leq 10^6, 0 \leq k, t \leq 10^9) — довжину масиву та параметри операцій.

Другий рядок містить $n$ цілих чисел a_1, a_2, \ldots, a_n (-10^{18} \leq a_i \leq 10^9) — початкові значення елементів масиву.

Вихідні дані

Виведіть одне ціле число $c$ — мінімальну кількість операцій, за яку можна зробити так, щоб всі елементи масиву стали меншими або рівними нулю. Якщо це зробити неможливо, то виведіть $-1$.

Якщо це зробити можливо, то виведіть $n$ цілих чисел cnt_i (1 \leq i \leq n), які позначають кількість операцій, які були виконані над елементом з індексом $i$. Зверніть увагу, що має виконуватися рівність \sum\limits_{i=1}^n cnt_i = c.

Приклади

Оцінювання

1. ($3$ бали) t = 0;

2. ($5$ бали) 1 \leq n \leq 300, 0 \leq |a_i| \leq 300, 0 \leq t \leq 10^6;

3. ($8$ балів) 1 \leq n \leq 3000, 0 \leq |a_i| \leq 3000, 0 \leq t \leq 10^6;

4. ($9$ балів) 1 \leq n \leq 10^3, 1 \leq a_i \leq 10^9, 0 \leq t \leq 10^6;

5. ($5$ балів) 1 \leq n \leq 10^4, 1 \leq a_i \leq 10^9;

6. ($13$ балів) 1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9;

7. ($8$ балів) 1 \leq a_i \leq 10^9;

8. ($9$ балів) 1 \leq n \leq 10^3, 0 \leq t \leq 10^6;

9. ($5$ балів) 1 \leq n \leq 10^4;

10. ($14$ балів) 1 \leq n \leq 10^5;

11. ($21$ бал) без додаткових обмежень.