var scale;
var magic;
var shadow;
var MAX = 20;
var MIN = 3;
var allstep = 0;
var mystep = 0;
var MaxStep = 100000;

function BackShadow()
{
	var i, j;
	for(i=0; i<scale; i++)
	{
		for(j=0; j<scale; j++)
			shadow[allstep+1][i][j] = magic[i][j];
	}
}

//Initialize the magic
function InitMagic(n)
{
	var i, j;
	magic = new Array();
	shadow = new Array();
	scale = n;
	for(i=0; i<MaxStep; i++)
	{
		shadow[i] = new Array();
		for(j=0; j<n; j++)
			shadow[i][j] = new Array();
	}
	for(i=0; i<n; i++)
	{
		magic[i] = new Array();
		for(j=0; j<n; j++)
		{
			magic[i][j] = 0;	//initialize every position with 0
			shadow[allstep][i][j] = 0;
		}
	}
}

//Odd-number scale method of magic square
function OddMagic(offseti, offsetj, mymin, n)
{
	var tmpi, tmpj;		//save last number's position
	var i;

	tmpi = 0; tmpj = parseInt(n/2);
	magic[tmpi + offseti][tmpj + offsetj] = mymin;	//the middle of first line is min
	BackShadow();
	shadow[++allstep][tmpi + offseti][tmpj + offsetj] = magic[tmpi + offseti][tmpj + offsetj];
	
	for(i=2; i<=n*n; i++)
	{
		tmpi = (tmpi - 1 + n) % n;
		tmpj = (tmpj + 1) % n;

		//check proper position
		if(magic[tmpi + offseti][tmpj + offsetj] != 0)
		{
			tmpi = (tmpi + 2) % n;
    		tmpj = (tmpj - 1 + n) % n;
		}
		magic[tmpi + offseti][tmpj + offsetj] = i + mymin - 1;
		BackShadow();
		shadow[++allstep][tmpi + offseti][tmpj + offsetj] = magic[tmpi + offseti][tmpj + offsetj];
	}
}

//Double-even-number scale method of magic square(4N)
function DoubleEvenMagic(n)
{
	var sum;
	var tmp, ri, rj;	
	var i, j;

	tmp = 1;
	sum = n*n+1;
	
	//original number 
	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			magic[i][j] = (tmp ++);
			BackShadow();
			shadow[++allstep][i][j] = magic[i][j];
		}
	}

	//find proper position and replace it with complementary number
	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			ri = i % 4;
			rj = j % 4;

			//find proper position
			if(((ri == 0 || ri == 3) && (rj == 0 || rj == 3)) || 
			   ((ri == 1 || ri == 2) && (rj == 1 || rj == 2)))
			{
				//replace with complementary number
				magic[i][j] = sum - magic[i][j];
				BackShadow();
				shadow[++allstep][i][j] = magic[i][j];
			}
		}
	}
}

//Single-even-number scale method of magic square(4N+2)
function SingleEvenMagic(n)
{
	var i, j, k;
	var startj;
	var tmp;

	//create four odd magic matrixs
	OddMagic(0, 0, 1, n/2);						//A
	OddMagic(n/2, n/2, (n/2)*(n/2) + 1, n/2);	//D
	OddMagic(0, n/2, 2*(n/2)*(n/2) + 1, n/2);	//B
	OddMagic(n/2, 0, 3*(n/2)*(n/2) + 1, n/2);	//C

	k = (n - 2) / 4;
	for(i = 0; i < n / 2; ++ i)
	{
		//A and C exchange
		if(i == k)
			startj = k;
		else
			startj = 0;
		for(j = startj; j < startj + k; ++ j)
		{
			tmp = magic[i][j];
			magic[i][j] = magic[i + n/2][j];
			BackShadow();
			shadow[++allstep][i][j] = magic[i][j];
			magic[i + n/2][j] = tmp;
			BackShadow();
			shadow[++allstep][i + n/2][j] = magic[i + n/2][j];
		}

		//B and D exchange
		startj = n - 1 - k;
		for(j = startj; j > startj - k + 1; -- j)
		{
			tmp = magic[i][j];
			magic[i][j] = magic[i + n/2][j];
			BackShadow();
			shadow[++allstep][i][j] = magic[i][j];
			magic[i + n/2][j] = tmp;
			BackShadow();
			shadow[++allstep][i + n/2][j] = magic[i + n/2][j];
		}
	}
}

//Check input whether legal and calculate
function GetMagic(n)
{
	if(n > MAX || n < MIN)
	{
		alert("The scale must be %d--%d!\n", MIN, MAX);
		return;
	}
	
	InitMagic(n);

	if(n % 2 == 1)
		OddMagic(0, 0, 1, n);
	else if(n % 4 == 0)
		DoubleEvenMagic(n);
	else
		SingleEvenMagic(n);
}