Chèn x trước lần xuất hiện cuối cùng của y (Insert x Before the Last Occurrence of y)

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

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

Đề bài

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

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

Cho thêm hai số nguyên $x$ và $y$. Đặt tập chỉ số của các lần xuất hiện của $y$ là

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

Nếu $I\ne\varnothing$ và $n<C$, đặt

$$p=\max I,$$

rồi chèn $x$ ngay trước $a_p$. Mảng mới có kích thước $n+1$ và thỏa

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

Nếu $I=\varnothing$ hoặc $n=C$, không thực hiện chèn và mảng giữ nguyên. Hãy in kích thước logic và mảng sau thao tác.

Input

Dòng đầu chứa hai số nguyên $C$ và $n$. Dòng thứ hai chứa $n$ số nguyên $a_0,\ldots,a_{n-1}$. Dòng thứ ba chứa $x$ và $y$.

Output

Dòng đầu in kích thước logic sau thao tác. Dòng thứ hai in các phần tử đang thuộc mảng logic theo thứ tự.

Subtask

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

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

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

Ví dụ

Input

8 6
4 2 7 2 9 5
100 2

Output

7
4 2 7 100 2 9 5

Giải thích

Giá trị $y=2$ xuất hiện ở các chỉ số $1$ và $3$, nên $p=3$. Vì $n<C$, chèn $x=100$ tại chỉ số $3$ mới và dịch đoạn từ chỉ số $3$ cũ sang phải.