ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural FU Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Prime Square

Time limit: 1.0 second
Memory limit: 64 MB
In this problem we consider n × n tables filled with integers from 1 to n2 in such a way that the following conditions are satisfied.
  1. Each number occurs exactly once in the table.
  2. 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
To submit the solution for this problem go to the Problem set: 1985. Prime Square