Problem C: We only want the smallest

Problem C: We only want the smallest

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 3704  Solved: 745
[Submit][Status][Web Board]


We construct an array \(C\) out of two given array \(A\) and \(B\) such that each element in array \(C\) is the product of an element in \(A\) and an element in \(B\). For example, we have \(A=[1,2,1]\) and \(B=[5,2]\) , then \(C=[5,2,10,4,5,2]\)

Now we only want to know the first \(K\) smallest element of array \(C\).


The first line contains three integers \(N\), \(M\) and \(K\), denoting the length of array \(A\), the length of array \(B\) and \(K\) smallest respectively.\((1\leq N,M\leq 5\times 10^5),K\leq Min(5\times 10^5,N\times M)\)

The second line contains \(N\) integers \(A_1,A_2,...A_N(1\leq A_i\leq 10^9)\)

The third line contains \(M\) integers \(B_1,B_2,...B_M(1\leq B_i\leq 10^9)\)


Output \(K\) integers separated by spaces in ascending order, denoting the first \(K\) smallest elements in \(C\).

Sample Input

3 2 6
1 2 1
5 2

Sample Output

2 2 4 5 5 10