Let p a prime number. A set F_p={0, 1 ... p-1} equipped with the mod p addition and multiplication is a finite field. In this problem you have to compute the multiplicative inverse of some F_p valued (quadratic) matrices.

The input consists of blocks. The structure of a block is:

n p

A_{1, 1} ... A_{1, n}

...

A_{n, 1} ... A_{n, n}

where p is a prime number, 1ij are in F_p. The last block followed by 0 0.

The output for each block is either the multiplicative inverse of a given matrix if it exists or the word "singular"

Example

Input:

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

3 7
3 5 0 
0 5 1 
6 6 6 

2 2
1 1 
1 0 

3 5
4 0 0 
2 4 1 
0 2 3 

3 7
0 1 4 
6 1 2 
2 1 1 

0 0

Output:

0 1 0 1 
0 0 1 1 
1 1 0 0 
0 0 1 0 

6 3 3 
5 1 1 
3 3 2 

0 1 
1 1 

singular

singular