In this problem we consider n
filled with integers from 1 to n2
in such a way that the following conditions are satisfied.
- Each number occurs exactly once in the table.
- For each i from 2 to n2 the cells of the
table that contain i and i − 1 must have a shared side.
Let’s define a primality of a column as the number of its cells
containing prime numbers, and a primality of a table as the
maximum primality of all its columns.
Find the table with the maximum primality among all
tables that satisfy the stated conditions.
The only line contains an integer n (1 ≤ n ≤ 256).
Output the required table. If there are several tables with the maximum
primality, you may output any of them.
2 1 12 11
3 16 13 10
4 15 14 9
5 6 7 8
The primality of the table in the sample output is equal to 3 (this is the primality of its first column).
Problem Author: Mikhail Rubinchik, special thanks to Alexander Ipatov
Problem Source: Open Ural FU Championship 2013