배열 조인

정수 배열 $A = [a_1, a_2, \ldots, a_n]$과 $B = [b_1, b_2, \ldots, b_m]$이 주어진다. $A$와 $B$의 $k$-join은 길이가 $k$인 배열 중 사전순으로 가장 작은 배열 $R$이다. $R$은 비어 있지 않은 두 부분수열로 나눌 수 있는데, 첫 번째는 $A$의 부분수열이고 두 번째는 $B$의 부분수열이다.

형식적으로는 다음 조건을 만족하는 $R = [r_1, r_2, \ldots, r_k]$를 찾아야 한다. 비어 있지 않은 인덱스 수열 $1 \le i_{1,1} < i_{1,2} < \ldots < i_{1,t} \le n$과 $1 < j_{1,1} < j_{1,2} < \ldots < j_{1,k-t} \le m$이 있고, 인덱스 수열 $1 \le i_{2,1} < i_{2,2} < \ldots < i_{2,t} \le k$와 $1 \le j_{2,1} < j_{2,2} < \ldots < j_{2,k-t} \le k$가 있어서 다음이 성립해야 한다.

• 모든 $1 \le p \le t$, $1 \le q \le k - t$에 대해 $i_{2,p} \ne j_{2,q}$이다.
• 모든 $1 \le p \le t$에 대해 $a_{i_{1,p}} = r_{i_{2,p}}$이다.
• 모든 $1 \le p \le k - t$에 대해 $b_{j_{1,p}} = r_{j_{2,p}}$이다.

예를 들어 $A = [1, 2, 1, 3, 1, 2, 1]$, $B = [1, 2, 3, 1]$, $k = 9$이면 $k$-join은 $R = [1, 1, 1, 1, 2, 1, 2, 3, 1]$이다(첫 번째 배열에서 온 부분수열은 $[1, 1, 1, 2, 1]$, 두 번째 배열에서 온 부분수열은 $[1, 2, 3, 1]$).

주어진 두 배열 $A$, $B$와 정수 $k$에 대해 $k$-join $R$을 구하라.

첫 번째 줄에 배열 $A$의 길이 $n$이 주어진다 ($1 \le n \le 3000$).

두 번째 줄에 $A$의 원소 $a_i$가 $n$개 주어진다 ($1 \le a_i \le 3000$).

세 번째 줄에 배열 $B$의 길이 $m$이 주어진다 ($1 \le m \le 3000$).

네 번째 줄에 $B$의 원소 $b_i$가 $m$개 주어진다 ($1 \le b_i \le 3000$).

마지막 줄에 정수 $k$가 주어진다 ($2 \le k \le n + m$).

주어진 배열의 $k$-join을 출력한다.