Chèn x sau lần xuất hiện đầu tiên của y (Insert x After the First Occurrence of y)

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à kích thước logic hiện tại $n$, với

Dãy đang sử dụng là $a_0,a_1,\ldots,a_{n-1}$. Cho hai số nguyên $x$ và $y$.

Đặt

• Nếu $I=\varnothing$, không thay đổi mảng.
• Nếu $I\ne\varnothing$ nhưng $n=C$, mảng đã đầy nên không thể chèn; giữ nguyên mảng.
• Nếu $I\ne\varnothing$ và $n<C$, đặt $p=\min I$ và chèn $x$ ngay sau vị trí $p$. Khi đó kích thước mới là $n+1$ và mảng mới $b$ thỏa

Hãy in kích thước logic và nội dung mảng sau thao tác.

Input

Dòng đầu chứa $C$ và $n$. Dòng thứ hai chứa $n$ số nguyên $a_i$. 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 toàn bộ 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\le10$, $|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 100 7 2 9 5

Giải thích

Lần xuất hiện đầu tiên của $y=2$ ở chỉ số $1$. Vì $n<C$, chèn $100$ vào chỉ số mới $2$ và dịch đoạn còn lại sang phải.