P1631 Merging Sequences

There are two length-$N$ non-decreasing sequences $A, B$. Taking one number from $A$ and one number from $B$ and adding them yields $N^2$ sums. Find the smallest $N$ sums among these $N^2$ sums.

The first line contains a positive integer $N$. The second line contains $N$ integers $A_{1\dots N}$. The third line contains $N$ integers $B_{1\dots N}$.

Output one line with $N$ integers, from smallest to largest, representing these $N$ smallest sums.

For $50\%$ of the testdata, $N \le 10^3$. For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le a_i, b_i \le 10^9$. Translated by ChatGPT 5