Joining Arrays

Consider two arrays of integers $A = [a_1, a_2, \ldots, a_n]$ and $B = [b_1, b_2, \ldots, b_m]$. The $k$-join of $A$ and $B$ is the lexicographically smallest array $R$ of length $k$ that can be split into two non-empty subsequences, where the first is a subsequence of $A$ and the second is a subsequence of $B$.

Formally, you need to find the array $R = [r_1, r_2, \ldots, r_k]$ for which there exist two non-empty index sequences $1 \le i_{1,1} < i_{1,2} < \ldots < i_{1,t} \le n$ and $1 < j_{1,1} < j_{1,2} < \ldots < j_{1,k-t} \le m$, and two index sequences $1 \le i_{2,1} < i_{2,2} < \ldots < i_{2,t} \le k$ and $1 \le j_{2,1} < j_{2,2} < \ldots < j_{2,k-t} \le k$, such that:

• For each $1 \le p \le t$ and $1 \le q \le k - t$, we have $i_{2,p} \ne j_{2,q}$.
• For each $1 \le p \le t$, we have $a_{i_{1,p}} = r_{i_{2,p}}$.
• For each $1 \le p \le k - t$, we have $b_{j_{1,p}} = r_{j_{2,p}}$.

For example, if $A = [1, 2, 1, 3, 1, 2, 1]$, $B = [1, 2, 3, 1]$, and $k = 9$, their $k$-join is $R = [1, 1, 1, 1, 2, 1, 2, 3, 1]$ (the subsequence from the first array is $[1, 1, 1, 2, 1]$, and the subsequence from the second array is $[1, 2, 3, 1]$).

For two given arrays $A$ and $B$ and an integer $k$, find their $k$-join $R$.

The first line contains $n$, the length of array $A$ ($1 \le n \le 3000$).

The second line contains $n$ integers $a_i$, the elements of $A$ ($1 \le a_i \le 3000$).

The third line contains $m$, the length of array $B$ ($1 \le m \le 3000$).

The fourth line contains $m$ integers $b_i$, the elements of $B$ ($1 \le b_i \le 3000$).

The last line contains the integer $k$ ($2 \le k \le n + m$).

Output the $k$-join of the given arrays.