You are given two arrays A (size m) and B (size n). You have to choose some elements from A and B such that the resulting array (size d) is lexicographically maximum. The only constraint here is that you have to maintain the relative ordering of the elements taken from the same array.

Example 1

Input

4 6 5

2 3 5 4

8 0 1 4 7 2

Output

8 7 5 4 2

Example 2

Input

2 3 5

7 8

7 1 5

Output

7 8 7 1 5

Constraints:

1 < m, n ≤ 512

1 < d ≤ (m + n)

0 ≤ A[i], B[j] ≤ 9