Tích mảng nhỏ nhất

Cho mảng $a_1,a_2,\dots ,a_n$ gồm $n$ số nguyên và một số nguyên dương $x$. Một phép toán cho phép bạn chọn một chỉ số $i$ ($1\le i\le n$) và thay $a_i$ bằng $a_i+x$ hoặc $a_i-x$. Một phép toán có thể được áp dụng nhiều lần lên cùng một vị trí.

Bạn được phép thực hiện không quá $k$ phép toán. Hãy in ra mảng kết quả $b_1,b_2,\dots ,b_n$ sao cho tích $b_1·b_2·\dots ·b_n$ đạt giá trị nhỏ nhất có thể. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $k$, $x$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra $n$ số nguyên $b_1,b_2,\dots ,b_n$ — mảng sau khi áp dụng không quá $k$ phép toán sao cho tích các phần tử là nhỏ nhất có thể. Với mọi $i$, hiệu $b_i-a_i$ phải là một bội nguyên (có thể âm hoặc bằng $0$) của $x$, và tổng số phép toán ${\sum }_{i=1}^n\frac{|b_i-a_i|}{x}$ không vượt quá $k$.

Ràng buộc

• $1\le n,k\le 2·{10}^5$
• $1\le x\le {10}^9$
• $|a_i|\le {10}^9$

Ví dụ