Xây dựng dãy số

Cho hai dãy số nguyên dương $a_1,a_2,\dots ,a_m$ và $b_1,b_2,\dots ,b_n$. Các bạn cần xây dựng dãy $c$ gồm $k$ phần tử $c_1,c_2,\dots ,c_k$ thỏa các yêu cầu sau:

• Tồn tại một dãy con của dãy $c$ là dãy con của dãy $a$,
• Các phần tử còn lại của dãy $c$ là một dãy con của $c$ đồng thời là dãy con của dãy $b$,
• Dãy $c$ có thứ tự từ điển nhỏ nhất.

Nói cách khác, có thể chia các phần tử của $c$ thành hai nhóm, mỗi nhóm giữ nguyên thứ tự xuất hiện trong $c$: nhóm thứ nhất là một dãy con của $a$, nhóm thứ hai là một dãy con của $b$. Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử (có thể không xóa phần tử nào), các phần tử còn lại giữ nguyên thứ tự và không nhất thiết đứng liền nhau. Trong các dãy $c$ thỏa mãn hai điều kiện đầu, cần tìm dãy có thứ tự từ điển nhỏ nhất: dãy $c$ nhỏ hơn dãy $c^{\prime }$ (cùng độ dài $k$) nếu tại vị trí đầu tiên $i$ mà $c_i\ne c_i^{\prime }$ ta có $c_i<c_i^{\prime }$.

Chú ý: Dãy rỗng được coi là dãy con của mọi dãy nên nếu dãy $c$ là dãy con của chỉ một trong hai dãy đã cho cũng được coi là thỏa mãn hai điều kiện đầu tiên.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $m,n,k$ $(1\le m,n\le 3000;1\le k\le m+n)$.
• Dòng thứ hai chứa $m$ số $a_1,a_2,\dots ,a_m$.
• Dòng thứ ba chứa $n$ số $b_1,b_2,\dots ,b_n$.

Dữ liệu ra

In ra một dòng duy nhất chứa $k$ số của dãy $c$ tìm được, cách nhau bởi dấu cách.

Ràng buộc

• $1\le m,n\le 3000$
• $1\le k\le m+n$
• $1\le a_i,b_i\le {10}^9$

Subtasks

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

Ví dụ