The Balanced Allotment

A community garden is laid out as an n x n grid of plots, and the plots will be given the seed bags numbered 1 to n*n, one bag per plot. To be fair to every volunteer who looks after a row, a column or one of the two long diagonals, all these 2n + 2 lines must hold the same total of bag numbers.

Write balanced_allotment(n) for an odd n that returns the layout as a list of n rows, each a list of n integers. Every number from 1 to n*n must appear exactly once. Any layout with equal line totals is accepted.

Examples

Input:  n = 3
Output: [[8, 1, 6], [3, 5, 7], [4, 9, 2]]   (one of several valid answers)
Explanation: every row, column and diagonal sums to 15.

Input:  n = 1
Output: [[1]]

Constraints

• 1 <= n <= 99, and n is odd
• every line total must be n * (n*n + 1) // 2 (the numbers 1..n*n shared equally among n rows)

Goals

• Build a grid with a required property by a rule instead of by search
• Verify every row, column and diagonal of a square grid