Solved Problem - Merge K Sorted Arrays

Problem statement

Given $K$ sorted arrays of length $N$. Print the sorted set of $N*K$ integers after merging the arrays.

Input format

The first line of input consists of two space-separated integers $K(1 \leq K \leq 10^{3})$ and $N(1 \leq N \leq 10^{3})$.

The next $K$ lines consist of $N$ integers each, representing the $K$ arrays.

Output format

Print a single line of $K*N$ integers - the sorted merged array.

---

Sample

Input

3 4
1 3 5 7
3 7 9 11
2 4 6 8

Output

1 2 3 3 4 5 6 7 7 8 9 11

---

Explanation

The merged array is - $1,3, 5, 7, 3, 7, 9, 11, 2, 4, 6, 8$

The sorted array is - $1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9, 11$

---

Brute force

The naive approach would be to create a merged array of size $K*N$ and sort using any of the faster-sorting algorithms, the time complexity will be $O(K*N*log(K*N))$