Smallest N Sums of Two Sorted Arrays

Given two non-decreasing sequences \(A\) and \(B\) each of length \(N\), consider all \(N^2\) sums obtained by adding an element from \(A\) and an element from \(B\). Your task is to find the smallest \(N\) sums among these \(N^2\) sums.

Note: The sequences are given in non-decreasing (sorted) order. The answer should list the resulting \(N\) sums separated by a space, also in non-decreasing order.

Hint: An efficient approach is to use a min-heap to merge the sums since each row of \(A[i] + B[j]\) is already sorted through the ordering of \(A\) and \(B\>.

inputFormat

The first line contains a positive integer \(N\) indicating the length of each sequence. The second line contains \(N\) integers representing sequence \(A\) (in non-decreasing order). The third line contains \(N\) integers representing sequence \(B\) (in non-decreasing order).

outputFormat

Output the smallest \(N\) sums (from the \(N^2\) possible sums) in non-decreasing order, separated by a space.

sample

3
1 2 3
2 3 4

3 4 4