Array Reduction

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

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 $n$, $k$, $t$ ($1\le n\le 10^6$, $0\le k,t\le 10^9$) — the length of the array and the operation parameters.

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

Output

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

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

Examples

Scoring

1. ($3$ points) $t=0$;

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

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

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

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

6. ($13$ points) $1\le n\le 10^5,1\le a_i\le 10^9$;

7. ($8$ points) $1\le a_i\le 10^9$;

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

9. ($5$ points) $1\le n\le 10^4$;

10. ($14$ points) $1\le n\le 10^5$;

11. ($21$ points) without additional constraints.