A las vacas les encanta pasear en su pastizal cuadrado de longitud ~N~ ~(1 \leq N \leq 750)~ el cual está partido en ~NxN~ cuadrados. A ellas les gusta la vista, los olores, y el ambiente general de pasto y árboles.

Bessie ha decidido llevar a las vacas en el camino más largo posible comenzando en la esquina superior izquierda al centro (o cerca al centro en el caso de que ~N~ sea par) del pastizal, pasando a través y cada uno de los cuadrados en el camino después de empezar.

Ella ha decidido crear la ruta obvia en el sentido de las manecillas del reloj (hay un ejemplo a continuación) para su paseo vespertino. Escriba un programa que cree un mapa para ella que muestre el orden de los cuadrados que ella debe visitar.

Por ejemplo, para pastizales de tamaño ~N=3~ y ~N=4~, aquí están las rutas que Bessie debe usar:

1 2 3       1  2  3  4
8 9 4      12 13 14  5
7 6 5      11 16 15  6
           10  9  8  7

Entrada

Línea 1: Un solo entero: ~N~.

Salida

Líneas 1...N: ~N~ enteros separados por espacios.

Ejemplo de Entrada

3

Ejemplo de Salida

1 2 3
8 9 4
7 6 5

USACO Elite 2011 March Competition Bronze Division