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

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

A static array has capacity $C$ and current logical size $n$, where

The current array is $a_0,a_1,\ldots,a_{n-1}$. Given an insertion index $p$ and value $x$, where

Insert $x$ at index $p$. The new size is $n'=n+1$. The result $b$ satisfies

and

Print the new size and the resulting array.

Input

The first line contains integers $C,n,p,x$. If $n>0$, the second line contains $n$ integers $a_0,a_1,\ldots,a_{n-1}$.

Output

Print $n+1$ on the first line. Print the array after insertion on the second line.

Subtask

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

Example

Input

6 4 2 99
10 20 30 40

Output

5
10 20 99 30 40

Explanation

The old elements from index 2 onward shift one position to the right, then $99$ is stored at index 2.