Chèn x tại vị trí p (Insert x at Position p)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một mảng tĩnh có sức chứa $C$ và hiện có kích thước logic $n$, với

Mảng hiện tại là $a_0,a_1,\ldots,a_{n-1}$. Cho vị trí chèn $p$ và giá trị $x$, trong đó

Hãy chèn $x$ vào chỉ số $p$. Kích thước mới là $n'=n+1$. Mảng kết quả $b$ thỏa

và

Hãy in kích thước mới và mảng kết quả.

Input

Dòng đầu chứa bốn số nguyên $C,n,p,x$. Nếu $n>0$, dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\ldots,a_{n-1}$.

Output

Dòng đầu in $n+1$. Dòng thứ hai in mảng sau khi chèn.

Subtask

Subtask 1 (100 điểm): $1\le C\le2\cdot10^5$; $0\le n<C$; $0\le p\le n$; $|x|,|a_i|\le10^9$.

Ví dụ

Input

6 4 2 99
10 20 30 40

Output

5
10 20 99 30 40

Giải thích

Các phần tử cũ từ chỉ số 2 trở đi dịch sang phải một vị trí, sau đó $99$ được đặt tại chỉ số 2.