Problem 4 (Magic Square). (20 points) A magic-square is a nxn array where every number from 1 to na appears once in the array. The sum of numbers in every row, column and diagonal of the array is the same. See below for a 3 x 3 magic-square: 8 16 | 3 5 7 | 4 9 2 Suppose n = 3k for some integer k > 1, design an algorithm that outputs a nxn magic square. Analyze the running time of your algorithm. (There are many ways to solve this problem, but please try to use divide-and-conquer.)