Problem statement

Given two sorted arrays, $A[]$ and $B[]$, of sizes $N$ and $M$ respectively, merge them into a single array of size $N+M$ and print the array.

Input format

The first line consists of two space-separated integers $N, M$ $(1 \leq N,M \leq10^5)$.

The second line consists of $N$ space-separated integers representing the array $A[]$ $(1 \leq A[i] \leq 10^5)$.

The third line consists of $M$ space-separated integers representing the array $B[]$ $(1 \leq B[i] \leq 10^5)$.

Output format

Print a single line of output containing the $N+M$ integers representing the merged and sorted array $C[]$.

---

Sample

Input:

4 4
2 3 4 6
1 5 7 8

Output

1 2 3 4 5 6 7 8

---

Solution

We use 2 pointers $i$ and $j$ for $A[]$ and $B[]$ respectively.

At each step, we copy the smaller of $A[i], B[j]$ to the current end of $C[]$. Keep doing this until we reach the end of A or B. After that only one array remains (either $A$ or $B$), copy all the remaining elements to C.

See the illustration for better understanding.