Múa lân

Múa Lân là một tiết mục trong lễ hội ăn mừng đội tuyển Việt Nam vô địch AFF Cup 2018. Khi chơi múa lân, hai người trong lốt của một con lân sẽ biểu diễn những tiết mục nhào lộn thăng bằng rất hấp dẫn. Người đứng trước đứng thẳng giữ đầu lân và hai chân có vai trò như hai chân trước của con lân. Người đứng sau cúi xuống lưng người thứ nhất và hai chân có vai trò như hai chân sau của con lân.

Có hai dãy cột, mỗi dãy xếp hàng dọc và đánh số từ $1$ tới $n$, ký hiệu là dãy $L$ và dãy $R$. Cột thứ $i$ của dãy $L$ và cột thứ $i$ của dãy $R$ gọi là ngang hàng nhau. Trong quá trình biểu diễn, chân trái (trước và sau) của con lân chỉ đặt lên cột ở dãy $L$ còn chân phải của nó chỉ đặt lên cột ở dãy $R$. Mỗi khi đặt chân, hai chân trước luôn đặt ở hai cột ngang hàng và cũng như vậy, hai chân sau cũng luôn phải đặt ở hai cột ngang hàng.

Ban đầu con lân đứng bằng hai chân sau: chân trái ở cột số $1$ dãy $L$ và chân phải ở cột số $1$ dãy $R$ (để thực hiện động tác này người đứng sau phải nâng người đứng trước lên), sau đó con lân đặt hai chân trước lên cột $2$ của mỗi dãy. Tiếp theo, con lân sẽ lần lượt nhảy qua dãy cột: mỗi bước nhảy, hai chân trước nhảy sang cặp cột ngang hàng kế tiếp cặp cột đang đứng và hai chân sau nhảy vào vị trí hai chân trước vừa đứng. Để tiết mục biểu diễn được an toàn, dãy các cột phải thỏa mãn hai điều kiện sau:

• Hai cột ở hai vị trí ngang hàng trên hai dãy phải có chiều cao bằng nhau.
• Chênh lệch độ cao giữa hai cột liên tiếp trong dãy $L$ cũng như chênh lệch độ cao giữa hai cột liên tiếp trong dãy $R$ không được vượt quá $\Delta$ (chênh lệch đúng bằng $\Delta$ vẫn được phép).

Bạn cần kiểm tra nếu dãy cột không tuân thủ quy tắc trên, bạn cần loại bỏ một số ít nhất các cột và dồn các cột còn lại trong mỗi dãy giữ nguyên thứ tự để được hai dãy cột thỏa mãn điều kiện cho buổi diễn (hai dãy còn lại cùng số cột $m$; các điều kiện xét trên các cột còn lại sau khi dồn). Cho biết độ cao của các cột trong dãy $L$ sau khi thực hiện công việc (dĩ nhiên đây cũng là độ cao của các cột trong dãy $R$). Nếu có nhiều phương án tối ưu, chỉ ra phương án có dãy độ cao của các cột mang thứ tự từ điển lớn nhất.

Nói cách khác, cần tìm dãy $c_1,c_2,\dots ,c_m$ dài nhất vừa là dãy con của dãy độ cao $L$, vừa là dãy con của dãy độ cao $R$, và thỏa mãn $|c_t-c_{t+1}|\le \Delta$ với mọi $1\le t<m$. Trong các dãy dài nhất, chọn dãy có thứ tự từ điển lớn nhất: dãy $c$ lớn hơn dãy $c^{\prime }$ (cùng độ dài) nếu tại vị trí đầu tiên $t$ mà $c_t\ne c_t^{\prime }$ ta có $c_t>c_t^{\prime }$. Nếu hai dãy không có độ cao chung nào thì $m=0$.

Dữ liệu vào

• Dòng $1$ chứa số nguyên dương $n$ và số nguyên dương $\Delta$.
• Dòng $2$ chứa $n$ số nguyên dương, số thứ $i$ là độ cao cột thứ $i$ của dãy $L$.
• Dòng $3$ chứa $n$ số nguyên dương, số thứ $i$ là độ cao cột thứ $i$ của dãy $R$.

Các số trên một dòng của input được ghi cách nhau bởi dấu cách.

Dữ liệu ra

• Dòng $1$ ghi số lượng cột còn lại trên mỗi dãy ($m$).
• Dòng $2$ ghi $m$ số nguyên là độ cao của các cột còn lại trong dãy $L$, các số phải được liệt kê theo thứ tự từ chiều cao cột đầu tiên đến chiều cao cột cuối cùng (nếu $m=0$ thì dòng này để trống).

Ràng buộc

• $1\le n\le 4000$
• $1\le \Delta \le {10}^9$
• Độ cao mỗi cột là số nguyên dương không vượt quá ${10}^9$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n\le 20$;
• Subtask 2 ($30\%$ số điểm): $n\le 100$;
• Subtask 3 ($50\%$ số điểm): Không có ràng buộc bổ sung.

Ví dụ