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

Дано масив $a$, який складається з $n$ цілих чисел. За одну операцію можна вибрати позицію $i$ ($1\le i\le n$), зменшити $a_i$ на $k$ та збільшити значення всіх інших елементів $a_j$ ($1\le j\le n,i\ne j$) на $t$.

Знайдіть мінімальну кількість операцій, за яку можна зробити так, щоб всі елементи масиву стали меншими або рівними нулю (тобто недодатними), або повідомте, що це зробити неможливо.

Вхідні дані

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

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

Вихідні дані

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

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

Приклади

Оцінювання

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

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

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

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

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

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

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

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

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

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

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