Algorithm

Don't try anything brutal, since one side of the grid can be up to (32 * 32 - 32 + 1 ) ** 2 = 993 . So, we must find a way to do this quick and the sentence k-1 will be 0, 1 or prime suggest that there is a special solution for primes. So, the first thing is to return to a (k - 1) ** 2 grid to use this primality property.

So let's take an example for k=4 so n=13.

	1	2	3	4	5	6	7	8	9	10	11	12	13
1	X	X	X	X
2	X				X	X	X
3	X							X	X	X
4	X										X	X	X
5		X
6		X
7		X
8			X
9			X
10			X
11				X
12				X
13				X

Now, we have a nice (k - 1) ** 4 hole in the bottom-right part of the matrix, but remember that (k - 1) ** 4 = ((k - 1) ** 2)** 2. So let's fill a (k - 1) ** 2 matrix with each matrix[i][j]=(i-1)*(j-1) this way :

	1	2	3
1	0	0	0
2	0	1	2
3	0	2	4

	1	2	3
1	1 2 3 1 X     2   X   3     X	1 2 3 1 X     2   X   3     X	1 2 3 1 X     2   X   3     X
2	1 2 3 1 X     2   X   3     X	1 2 3 1   X   2     X 3 X	1 2 3 1     X 2 X     3   X
3	1 2 3 1 X     2   X   3     X	1 2 3 1     X 2 X     3   X	1 2 3 1   X   2     X 3 X

You've done it!

Trick

Let me think... there are no real tricks for this one... Oh yes, :D! The algorithm was tricky!

If you are in trouble with the multi-entry input, read my how to read input.

Additional Input

135.in

Additional Output

135.out

Problem

Consider a grid such as the one shown. We wish to mark k intersections in each of n rows and n columns in such a way that no 4 of the selected intersections form a rectangle with sides parallel to the grid. Thus for k = 2 and n = 3, a possible solution is:

It can easily be shown that for any given value of k, is a lower bound on the value of n, and it can be shown further that n need never be larger than this.

Write a program that will find a solution to this problem for k<=32, k-1 will be 0, 1 or prime.

Input and Output

Input will consist of some values for k, one of each line. For each value of k, output will consist of n lines of k points indicating the selected points on that line. Print a blank line between two values of k.

Sample input

2
1

Sample output

1 2
1 3
2 3

1

Return to Volume I Explanations