Insert x Before the Last Occurrence of y

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

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

$$a_0,a_1,\ldots,a_{n-1},\qquad 1\le n\le C.$$

Given integers $x$ and $y$, define

$$I=\{i\mid 0\le i<n,\ a_i=y\}.$$

If $I\ne\varnothing$ and $n<C$, let $p=\max I$ and insert $x$ immediately before $a_p$. The new array has size $n+1$ and

$$b_i=\begin{cases} a_i,&0\le i<p,\\x,&i=p,\\a_{i-1},&p<i\le n.\end{cases}$$

If $I=\varnothing$ or $n=C$, leave the array unchanged. Print the final logical size and array.

Input

The first line contains $C$ and $n$. The second line contains $a_0,\ldots,a_{n-1}$. The third line contains $x$ and $y$.

Output

Print the final logical size on the first line and the active array elements on the second line.

Subtask

Subtask 1 (20 points): $1\le n\le C\le 10$, $|a_i|,|x|,|y|\le10^3$.

Subtask 2 (30 points): $1\le n\le C\le5000$, $|a_i|,|x|,|y|\le10^6$.

Subtask 3 (50 points): $1\le n\le C\le2\cdot10^5$, $|a_i|,|x|,|y|\le10^9$.

Example

Input

8 6
4 2 7 2 9 5
100 2

Output

7
4 2 7 100 2 9 5

Explanation

The output follows directly from the mathematical definition above.