Biến đổi

Cho dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, \ldots, A_N\).

Yêu cầu: Thực hiện biến đổi dãy \(A\) theo các yêu cầu sau:

• Lần lượt tăng \(X\) đơn vị đối với các số lẻ và giảm \(Y\) đơn vị đối với các số chẵn.

• Sắp xếp dãy số tăng dần theo thứ tự từ trái sang phải sau khi thay đổi giá trị.

Input

Dữ liệu vào:

• Dòng đầu chứa \(3\) số nguyên dương \(N, X, Y\) (\(1 \le N \le 10^6\); \(0 < X, Y < 10^3\)).

• Dòng thứ hai chứa dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, \ldots, A_N\) (\(1 \le A_i \le 10^8\)).
  Các số trên cùng một dòng cách nhau bởi dấu cách.

Ràng buộc:

• Subtask 1 (\(50\%\) số điểm): \(N \le 10^3\);

• Subtask 2 (\(40\%\) số điểm): \(N \le 10^6\);

• Subtask 3 (\(10\%\) số điểm): Không có ràng buộc nào thêm.

Output

In ra

• Dòng đầu ghi dãy số sau khi thay đổi giá trị.

• Dòng thứ hai ghi dãy số tăng dần theo thứ tự từ trái sang phải sau khi thay đổi giá trị.

Example

Input:

6 4 5
8 2 5 6 3 4

Output:

3 -3 9 1 7 -1
-3 -1 1 3 7 9

Note

Các số lẻ (\(5\), \(3\)) được cộng \(4\), các số chẵn (\(8, 2, 6, 4\)) bị trừ \(5\), ta được dãy \(3, -3, 9, 1, 7, -1\).