Problem: Ikshu and his prime matrix

Ikshu is in love with prime numbers. He has a matrix of size N X N and wants atleast 5 prime numbers in that matrix arranged like a cross as shown in figure. Let us call this matrix "new year matrix"
X   X   X   X    X
If matrix is not a "new year matrix" he can alter it with the operation as described below:

1) Choose an element from the matrix.

2)  Increment the value at the element by K assuring that value of
   element does not exceed 10000.

Above operation can be applied any number of times.

Example :

Let matrix be:
2 2 3
4 5 6
7 8 9
and k be 1

He can perform 2 operations on (3,3) to get a cross centered at (2,2) with prime numbers = [2,3,5,7,11]

constraints:
1 ≤ N ≤ 1000
1 ≤ K ≤ 5
1 ≤ any element of matrix ≤10000

Input:
First line on input contains two integer N and K which is the size of the matrix, followed by N X N matrix.
N is the size of the matrix
and K is the value which is allowed to be add to any element of matrix.

Output: 
First line of output contains "yes" if such cross is possible else it contains "no".
If answer is possible, second line contains the minimum number of operations and third line contains the co-ordinate of center of cross(assuming indexing to be 1-based)
If many such answers are possible, print the one with minimum row index, if many answers are possible with same minimum row index print the one with minimum col index

SAMPLE INPUT
3 1
2 2 3
4 5 6
7 8 9

SAMPLE OUTPUT
yes
2 
2 2

Solution (in PYTHON):

Solution:
import math

def getPrime(Max):
    used = [0] * Max
    
    for i in xrange( 4, Max, 2 ):
        used[i] = 1
    
    used[1] = 1
    for i in xrange( 3, int(math.sqrt(Max) + 1), 2 ):
        if used[i] == 1:
            continue
        for j in xrange( i * i, Max, i ):
            used[j] = 1
    
    return used
    
def main():
    N,K = map(int, raw_input().strip().split())
    A = []
    
    Max = 0
    for _ in xrange(N):
        A.append(map(int, raw_input().strip().split()))
        temp = max(A[-1])
        Max = max(Max, temp)
    
    DP = [0] * (Max + 1)
    used = getPrime(10001)
    
    length = 10001
    for i in xrange( 1, Max + 1 ):
        if used[i] == 0:
            continue
           
        if K > 1 and i % K == 0:
            DP[i] = 10 ** 10
            continue
        
        j = i
        cnt = 0
        while j < length:
            if used[j] == 0:
                DP[i] = cnt
                break
            j += K
            cnt += 1
        if j >= length:
            DP[i] = 10 ** 10
    
    for i in xrange(N):
        for j in xrange(N):
            A[i][j] = DP[A[i][j]]
    
    MinStep = 10 ** 10
    flag = False
    X = -1
    Y = -1
    for i in xrange( 1, N - 1 ):
        for j in xrange( 1, N - 1 ):
            Sum = 0
            if A[i][j] == 10 ** 10:
                continue
            if A[i - 1][j - 1] == 10 ** 10:
                continue
            if A[i - 1][j + 1] == 10 ** 10:
                continue
            if A[i + 1][j - 1] == 10 ** 10:
                continue
            if A[i + 1][j + 1] == 10 ** 10:
                continue
                
            Sum = A[i][j] + A[i - 1][j - 1] + A[i - 1][j + 1] + A[i + 1][j - 1] + A[i + 1][j + 1]
            if MinStep > Sum:
                MinStep = Sum
                flag = True
                X = i + 1
                Y = j + 1
    
    if flag == True:
        print "yes"
        print MinStep
        print X,Y
    else:
        print "no"
    
if __name__=="__main__":
    main()