Consider the following problem.

Input: $n^2$ distinct numbers in some arbitrary order.

Output: an $nn$ matrix containing the input numbers, and having all rows and all columns sorted in increasing order.

Example: $n=3,$ so $n^2=9.$ Say the $9$ numbers are the digits $1,2,$dots,$9.$ Possible outputs include:

$([1,4,7],[2,5,8],[3,6,9]),or([1,4,5],[2,6,7],[3,8,9])or([1,3,4],[2,5,8],[6,7,9])or([1,2,3],[4,5,6],[7,8,9])or$ dots

It is clear that we can solve this problem in time $2n^{2}logn$ by just sorting the input $($remember that $($:$log(n^2)=2logn\}$ and then outputting the first $n$ elements as the first row, the next $n$ elements as the second row, and so on$.$ Your job in this problem is to prove a matching $(n^{2}logn)$ lower bound in the comparison$-$based model of computation, i$.$e$.,$ a lower bound of $c{n}^{2}logn$ for some constant $c>0$ that is independent of $n.$ For simplicity, you can assume $n$ is a power of $2.$

Hint: You may use the facts that $m!>(\frac{m}{e}{)}^m$ and that and comparison based sorting algorithm must make at least $log(n!)=(nlogn)$ comparisons.