Array Reduction#257
Sign in

Array Reduction

5 seconds
512 megabytes
Hard

Given an array consisting of integers. For one operation, you can choose position (1 \leq i \leq n), decrease a_i by , and increase the value of all other elements a_j (1 \leq j \leq n, i \neq j) by .

Find the minimum number of operations needed to make all elements of the array less than or equal to zero (i.e., non-positive), or report that it is impossible to do so.

Input

The first line contains three integers , , (1 \leq n \leq 10^6, 0 \leq k, t \leq 10^9) — the length of the array and the operation parameters.

The second line contains integers a_1, a_2, \ldots, a_n (-10^{18} \leq a_i \leq 10^9) — the initial values of the array elements.

Output

Output a single integer  — the minimum number of operations needed to make all elements of the array less than or equal to zero. If it is impossible, output .

If it is possible, output integers cnt_i (1 \leq i \leq n), which represent the number of operations performed on the element with index . Note that the equality \sum\limits_{i=1}^n cnt_i = c must hold.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  1. ( points) t = 0;

  2. ( points) 1 \leq n \leq 300, 0 \leq |a_i| \leq 300, 0 \leq t \leq 10^6;

  3. ( points) 1 \leq n \leq 3000, 0 \leq |a_i| \leq 3000, 0 \leq t \leq 10^6;

  4. ( points) 1 \leq n \leq 10^3, 1 \leq a_i \leq 10^9, 0 \leq t \leq 10^6;

  5. ( points) 1 \leq n \leq 10^4, 1 \leq a_i \leq 10^9;

  6. ( points) 1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9;

  7. ( points) 1 \leq a_i \leq 10^9;

  8. ( points) 1 \leq n \leq 10^3, 0 \leq t \leq 10^6;

  9. ( points) 1 \leq n \leq 10^4;

  10. ( points) 1 \leq n \leq 10^5;

  11. ( points) without additional constraints.