Problem Statement

You and $N$ merchants stand on a number line. The merchants are numbered $1, 2, \ldots, N$.

Initially, you are at coordinate $0$, and merchant $i$ is at coordinate $X_i$. Each merchant holds one item; the item held by merchant $i$ is called item $i$.

Your goal is to receive items $1, 2, \ldots, N$ in this order.

You may repeat any number of times, in any order, the following three operations:

• Move yourself by $1$. The cost of this operation is $C$.
• Choose one merchant and move that merchant by $1$. The cost of this operation is $D$.
• Choose one merchant, say merchant $i$. If you and merchant $i$ are at the same coordinate, and you have not yet received item $i$, then receive item $i$ from merchant $i$. Otherwise, do nothing. The cost of this operation is $0$.

Find the minimum total cost required to achieve the goal.

Also, output one possible combination of coordinates at which you receive each item when the total cost is minimized.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C, D \leq 10^5$
• $-10^5 \leq X_i \leq 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N C D
X_1 X_2 \ldots X_N

Output

Output two lines.

The first line should contain the minimal total cost required to achieve the goal.

The second line should contain $N$ integers $A_1, A_2, \ldots, A_N$ separated by spaces. Here, there must exist a sequence of operations that satisfies both of the following conditions:

• The goal is achieved, with the minimum possible total cost.
• For every integer $i$ such that $1 \leq i \leq N$, you receive item $i$ at coordinate $A_i$.