시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Consider two arrays of integers A = [a1, a2, ..., an] and B = [b1, b2, ..., bm]. Let us introduce their k-join as a lexicographically smallest array R of length k, that can be divided to two non-empty subsequences, first of which is a subsequence of A, and the second one is a subsequence of B.
Formally speaking, you need to find such array R = [r1, r2, ..., rk], that there are two non-empty sequences of indices 1 ≤ i1,1 < i1,2 < ... < i1,t ≤ n and 1 < j1,1 < j1,2 < ... < j1,k-t ≤ m in the original arrays, and two sequences of indices 1 ≤ i2,1 < i2,2 < ... < i2,t ≤ k and 1 ≤ j2,1 < j2,2 < ... < j2,k-t ≤ k, such that:
For example if A = [1, 2, 1, 3, 1, 2, 1], B = [1, 2, 3, 1], and k = 9, their k-join is the array R = [1, 1, 1, 1, 2, 1, 2, 3, 1] (subsequence from the first array — [1, 1, 1, 2, 1], subsequence from the second array — [1, 2, 3, 1]).
For two given arrays A and B, and an integer k find their k-join R.
The first line of input contains n — length of array A (1 ≤ n ≤ 3000).
The second line contains n integers ai — array A (1 ≤ ai ≤ 3000).
The third line contains m — length of array B (1 ≤ m ≤ 3000).
The fourth line contains m integers bi — array B (1 ≤ bi ≤ 3000).
The last line contains integer k (2 ≤ k ≤ n + m).
Output k-join of the given arrays.
7 1 2 1 3 1 2 1 4 1 2 3 1 9
1 1 1 1 2 1 2 3 1
Contest > Russian Code Cup > 2017 > RCC 2017 Elimination Round E번