Cho một mảng gồm \(N\) số nguyên và một số nguyên \(X\). Hãy thêm \(X\) vào các vị trí chẵn rồi in mảng sau khi thêm.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).
• Dòng thứ ba chứa số nguyên \(X\).

Output

• In ra mảng sau khi đã thêm \(X\) vào các vị trí chẵn, các phần tử cách nhau bởi dấu cách.

Constraints

• \(1 \leq N \leq 10^5\)
• \(|a_i|, |X| \leq 10^9\)

Example

4
1 2 3 4
5

1 5 2 5 3 5 4 5

5
6 12 9 20 1
10

6 10 12 10 9 10 20 10 1 10