//**************************************************************************
//	My first Java program
//	Author: Anirudh Modi (anirudh@bart.aero.psu.edu)
//	Date: 21/5/1998 - Thu
//**************************************************************************
import java.io.*;
import java.util.*;
import java.applet.*;
import java.awt.*;
//**************************************************************************
class MagicSquare
{
int N=5;
int square[][];

// Constructor
MagicSquare (int num)
	{
	 N = num;
	 square = new int [N+1][N+1];
	 if (N < 3)
	 	{
	 	 System.out.println("N >= 3 !!");
		 // System.exit(-1);
		}
	}

void make ()
	{
	 if (N < 3) return;

	 int n = N;
	 int c = 0;

	 if (n%2 == 0)
	 	{
		 if (n%4 == 0)
		 	{
		 	 while (n%2 == 0 && n > 4)
		 		{
			 	 n /= 2;
			 	 ++c;
				}
			 if (n == 4)
			 	FOUR(square);
			 else
			 	ODD(n,square);
			 if (c > 0)
			 	{
				 for (int l=1;l<=c;l++)
				 	{
					 n *= 2;
				 	 EVEN(n,square);
					}
				}
			}
		 else
		 	{
		 	 ODD(n/2,square);
		 	 EVEN(n,square);
			}
	 	}
	 else
	 	{
		 ODD(n,square);
		}
	}

void FOUR (int a[][])
	{
	 int p,i,j;
	 p = 4;
	 for (i=1;i<=p;i++)
	 	for (j=1;j<=p;j++)
			a[i][j] = p*(i-1)+j;

	 for (i=1;i<=p/2;i++)
	 	{
		 j = p-i+1;
		 int k = a[i][i];
		 a[i][i] = a[j][j];
		 a[j][j] = k;

		 k = a[i][j];
		 a[i][j] = a[j][i];
		 a[j][i] = k;
		}
	}

void ODD (int n, int a[][])
	{
	 int i,j,k;

	 for (i=1;i<=n;i++)
	 	for (j=1;j<=n;j++)
			a[i][j] = 0;
	 i = 1;
	 j = (n+1)/2;
	 a[i][j] = 1;
	 for (k=2;k<=n*n;k++)
	 	{
		 i += n*(1/i)-1;
		 j += n*(1/j)-1;
		 if (a[i][j] == 0)
		 	a[i][j] = k;
		 else
		 	{
			 i += 2-n*(i/n);
			 j += 1-n*(j/n);
			 a[i][j] = k;
			}
		}
	}

void EVEN (int n, int a[][])
	{
	 int n2,n4,i,j,k,s,m;
	 
	 n2 = n/2;
	 n4 = n/4;
	 for (i=1;i<=n2;i++)
	 	for (j=1;j<=n2;j++)
			{
			 k = a[i][j];
			 a[i][j+n2] = k;
			 a[i+n2][j] = k;
			 a[i+n2][j+n2] = k;
			}
	 s = n*n/4;
	 if (n%4 == 0)
	 	{
		 for (i=1;i<=n;i++)
		 	{
			 k = (2*i-2)/n;
			 for (j=1;j<=n4;j++)
			 	{
				 a[i][j] += 3*s*k;
				 a[i][j+n4] += 3*s*(1-k);
				 a[i][j+n2] += s*(2-k);
				 a[i][j+3*n4] += s*(1+k);
				}
			}
		}
	 else
		{
		 m = n4+1;
		 for (i=1;i<=2;i++)
			{
			 k = a[m][1];
			 a[m][1] = a[m][n4+1];
			 a[m][n4+1] = k;
			 m += n2;
			}
		 for (i=1;i<=n;i++)
		 	{
			 k = (2*i-2)/n;
			 for (j=1;j<=n4;j++)
				a[i][j] += 3*s*(1-k);
			 for (j=n4+1;j<=n2;j++)
				a[i][j] += 3*s*k;
			 for (j=n2+1;j<=n-n4+1;j++)
				a[i][j] += s*(2-k);
			 for (j=n-n4+2;j<= n;j++)
				a[i][j] += s*(1+k);
			}
		 m = n4+1;
		 for (i=1;i<=2;i++)
		 	{
			 k = a[m][1];
			 a[m][1] = a[m][n4+1];
			 a[m][n4+1] = k;
			 m += n2;
			}
		}
	}

int value (int i, int j)
	{
	 return square[i][j];
	}

void print ()
	{
	 if (N < 3) return; 

	 System.out.println("\nTHE MAGIC SQUARE OF " + N + " x " + N 
		+ " IS :-");
	 System.out.println("---------------------------------\n");
	 for (int i=1;i<=N;i++)
		{
	 	 for (int j=1;j<=N;j++)
			System.out.print(square[i][j] + " ");
	 	 System.out.print("\n");
		}
	}

void check ()
	{
	 if (N < 3) return;

	 long lsum = N*(N*N+1)/2,k;
	 long sum = N*lsum;
	 int i,j;

	 for (i=1;i<=N;i++)
	 	{
		 k = 0;
		 for (j=1;j<=N;j++)
		 	k += square[i][j];
		 if (k != lsum)
		 	System.out.println("ERROR!!!!");
		}

	 System.out.print("\nTHE SUM OF EACH ROW,COLUMN AND ");
	 System.out.print("PRINCIPAL DIAGONAL IS " + lsum + ".\n");
	 System.out.print("\nTHE SUM OF ALL THE NUMBERS USED (i.e. ");
	 System.out.print("from 1 to " + N*N + ") IS " + sum + ".\n");
	}
}
//**************************************************************************
public class applet extends Applet 
{
  MagicSquare M;
  int textheight=13,textwidth=30;
  int n=3;
  TextField Ntext;
  Label Nlabel;
  Button start;
  TextArea T;

  public void init ()
  	{
	 T = new TextArea(30,30);
	 Ntext = new TextField ("3",4);
	 add(Ntext);
	 Nlabel = new Label ("N");
	 add(Nlabel);
	 start = new Button("Start");
	 add(start);
	 MakeSquare(n);
  	}

  public void MakeSquare (int n)
	{
	 n = Integer.parseInt(Ntext.getText().trim());
 	 M = new MagicSquare(n);
 	 M.make();
 	 //M.print();
 	 //M.check();
	 repaint(10,10,1000,1000);
	}

  public boolean action(Event ev, Object arg)
	{
	 if (ev.target instanceof Button)
		{
		 String label = (String)arg;
		 if (label.equals("Start"))
			{
			 n = Integer.parseInt(Ntext.getText().trim());
		 	 MakeSquare(n);
			}
		}
	 return true;
	}
  
  public void paint (Graphics g) 
  	{
	 if (n < 3) 
		{
		 g.drawString("N >= 3",60,60);
		 return; 
		}

	 g.drawString("THE MAGIC SQUARE OF " + n + " x " + n 
		+ " IS :-",40,50);
	 for (int i=1;i<=n;i++)
		{
	 	 for (int j=1;j<=n;j++)
			g.drawString(M.value(i,j) + " ",40+textwidth*(j-1),
				70+textheight*i);
		}
	 long lsum = n*(n*n+1)/2;
	 long sum = n*lsum;
	 g.drawString("The sum of each row, column and "
		+"principal diagonal is " + lsum,40,70+textheight*(n+2));
	 g.drawString("The sum of all the numbers used (i.e. " 
		+"from 1 to " + n*n + ") is " + sum,40,70+textheight*(n+3));
	}
}
//**************************************************************************