Kattis

# Prime Matrix

Image by Chris

A Prime Matrix is defined as an $n \times n$ square matrix satisfying:

• All numbers in the matrix are positive integers, and

• The numbers in each row are distinct, and

• The numbers in each column are distinct, and

• The sum of numbers in each row is a prime number, and

• The sum of numbers in each column is a prime number.

There may be multiple valid prime matrices out there, but you don’t want the numbers in the matrix to be too large. Given a bound $b$, can you find a prime matrix so that it contains only integers between $1$ and $b$?

## Input

The input has a single line with two integers: $n$ ($2 \leq n \leq 50$) and $b$ ($2 \leq b \leq 10^9$).

## Output

Output any valid $n \times n$ prime matrix. The output must have $n$ rows. Each row must have $n$ space-separated integers between $1$ and $b$ without leading zeroes. If no such matrix exists, output “impossible”.

Sample Input 1 Sample Output 1
3 9

1 2 8
7 1 3
3 4 6

Sample Input 2 Sample Output 2
3 3

impossible