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

USU Championship 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Coupons

Time limit: 1.0 second
Memory limit: 64 MB
On the first day of the Petrozavodsk Training Camp, every participant is given meal coupons, which can be used in the dining-hall of the Petrozavodsk State University. This year the camp lasts for N2 days, and there is a separate coupon for each day. In order to make the coupons, the organizers have printed tables N × N on sheets of green paper. Each table contains numbers from 1 to N2, which are numbers of days for which coupons apply. Participants must cut their tables into N2 cells in order to obtain N2 coupons: one coupon per one day of the camp.
This year, when Dima received his sheet with coupons, he noticed that in the ith row and jth column of the printed table there was the number N(i – 1) + j (rows and columns are numbered from 1). Cells of the table are adjacent if they have a common side. Dima is a mathematician, so he quickly found two adjacent cells with the maximal sum of numbers in them. It turned out that the maximal sum was 2N2 – 1. Now Dima wants to find an order of coupons in the table such that the maximal sum of numbers in two adjacent cells is minimal. Dima has N2 days to find such a table. Can you do it in five hours?

Input

The input contains the integer 2 ≤ N ≤ 50.

Output

In the first line, output the required minimal value. Then output a table that provides this minimum by giving N numbers in each of the next N lines. If several answers are possible, you may output any of them.

Sample

inputoutput
2
6
1 4
3 2
Problem Author: Sergey Pupyrev
Problem Source: The XIth USU Programing Championship, October 7, 2006
To submit the solution for this problem go to the Problem set: 1480. Coupons