Problem:


写真に写っている景色は?

 A 君は会津に観光にやってきました。宿泊したホテルの窓からは会津盆地が一望できます。景色を眺めていると、床に写真の切れ端が落ちているのに気がつきました。どうやら窓から外の景色を撮ったようです。「どの辺りを撮ったのかな」と、A 君は窓の外の景色と写真が同じ大きさになるように写真をかざして、写真と窓の外の景色が一致する場所を探し始めました。

 それでは、A 君がやっていることをコンピュータでやってみましょう。窓の外の景色を n &times; n マスの正方形に分割します (n を景色の大きさと呼びます)。各マスには、そのマスの画像の情報を表す 0 以上の整数が書かれています。マスの位置は座標 (x, y) で表します。各マスの座標は以下の通りになります。

 写真の切れ端は、m &times; m マスの正方形で表されます (m を写真の切れ端の大きさと呼びます) 。この正方形の中で、切れ端の部分のマスには画像の情報が、切れ端に含まれない部分のマスには -1 が書かれています。たとえば、下図では、色が塗られている部分が実際の写真の切れ端の形を表しています。切れ端に穴が開いていることはありますが、必ず 1 つにつながっています。 (0 以上の値をもつマスが頂点だけで接しているときは、つながっていないものとみなします。) また、値 -1 のマスが縦または横 1 列に端から端まで並ぶことはありません。

  窓から見える景色の中で、写真の切れ端を 0、90、180、270 度回転させたいずれかと一致する領域を探します。たとえば、景色が下図のように表わせるとき、上図の切れ端を反時計回りに90 度回転させると、色が塗られた領域に一致します。

 窓から見える景色と写真の切れ端の情報を入力とし、景色の中で、切れ端を 0、90、180、270 度回転させたいずれかと一致する領域の最も上端に近いマスのうち、最も左端に近いマスの座標を出力するプログラムを作成してください。

 一致する領域が複数ある場合は、それらの領域内にあるマスの中で、最も上端に近いマスのうち、最も左端に近いマスの座標を出力してください。一致する領域がないときは、NA と出力します。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下の形式で与えられます。

n m
w11 w12 ... w1n
w21 w22 ... w2n
:
wn1 wn2 ... wnn
p11 p12 ... p1m
p21 p22 ... p2m
:
pm1 pm2 ... pmm

1 行目にn, m (1 ≤ n ≤ 100, 1 ≤ m ≤ 50, m ≤ n) が与えられます。

続く n 行に窓から見える景色の情報 wij (0 ≤ wij ≤ 15)、続く m 行に写真の切れ端のデータの情報 pij (-1 ≤ pij ≤ 15) が与えられます。

データセットの数は 100 を超えません。

Output

入力データセットごとに、マスの位置の座標または NA を１行に出力します。

Sample Input

8 4
2 1 3 1 1 5 1 3
2 3 2 4 1 0 2 1
0 3 1 2 1 1 4 2
1 2 3 2 1 1 5 4
0 2 0 1 1 3 2 1
1 3 1 2 2 4 3 2
5 1 2 1 4 1 1 5
4 1 1 0 1 2 2 1
2 -1 -1 -1
0 3 -1 -1
-1 2 2 4
-1 1 -1  1
5 3
1 0 2 3 5
2 3 7 2 1
2 5 4 2 2
8 9 0 3 3
3 6 0 4 7
-1 -1 2
-1 3 5
0 4 -1
0 0

Output for the Sample Input

4 2
NA



Sample input:
8 4
2 1 3 1 1 5 1 3
2 3 2 4 1 0 2 1
0 3 1 2 1 1 4 2
1 2 3 2 1 1 5 4
0 2 0 1 1 3 2 1
1 3 1 2 2 4 3 2
5 1 2 1 4 1 1 5
4 1 1 0 1 2 2 1
2 -1 -1 -1
0 3 -1 -1
-1 2 2 4
-1 1 -1  1
5 3
1 0 2 3 5
2 3 7 2 1
2 5 4 2 2
8 9 0 3 3
3 6 0 4 7
-1 -1 2
-1 3 5
0 4 -1
0 0


Sample output:
4 2
NA

Submission status: Wrong Answer

Solution code:
from sys import stdin
readline = stdin.readline


from itertools import product
from operator import itemgetter
from math import isinf


def scrap_top_left(picture):
    for py, px in product(range(len(picture)), repeat=2):
        if picture[py][px] != -1:
            return px, py


def is_match(window, picture, wx, wy):
    for py, px in product(range(len(picture)), repeat=2):
        if picture[py][px] == -1:
            continue
        if window[wy + py][wx + px] != picture[py][px]:
            return False
    return True


def search(window, picture):
    for wy, wx in product(range(len(window) - len(picture)), repeat=2):
        if is_match(window, picture, wx, wy):
            px, py = scrap_top_left(picture)
            return wx + px + 1, wy + py + 1
    return float('inf'), float('inf')


# http://d.hatena.ne.jp/odz/20070622/1182497414
def rotate_clockwise(matrix):
    return [list(row) for row in zip(*reversed(matrix))]


while True:
    window_size, picture_size = map(int, readline().split())
    if window_size == 0:
        break
    window = [list(map(int, readline().split())) for _ in range(window_size)]
    picture = [list(map(int, readline().split())) for _ in range(picture_size)]
    top_left = []
    for _ in range(4):
        top_left.append(search(window, picture))
        picture = rotate_clockwise(picture)
    top_left = min(top_left, key=itemgetter(1, 0))
    if isinf(top_left[0]):
        print('NA')
    else:
        print(*top_left)

Submission status: Wrong Answer

Solution code:
def main(piece, c):
    for h in range(n-m+1):
        for w in range(n-m+1):
            if f(piece, h, w):
                return
    else:
        if c != 4:
            move(piece, c)
        else:
            print 'NA'

def f(piece, h, w):
    ans = None
    for _h in range(m):
        for _w in range(m):
            if piece[_h][_w] != '-1':
                if piece[_h][_w] == picture[h+_h][w+_w]:
                    if ans is None:
                        ans = (w+_w+1, h+_h+1)
                else:
                    return
    else:
        print ans[0], ans[1]
        return True
    
def move(piece, c):
    _piece = []
    for w in range(m):
        lis = []
        for h in range(m):
            lis.append(piece[h][w])
        else:
            lis.reverse()
            _piece.append(lis)
    else:
        main(_piece, c+1)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    picture = [raw_input().split() for i in range(n)]
    piece = [raw_input().split() for i in range(m)]
    main(piece, 1)

Submission status: Wrong Answer

Solution code:
def main(piece, c):
    for h in range(n-m+1):
        for w in range(n-m+1):
            if f(piece, h, w):
                break
    if c != 4:
        move(piece, c)

def f(piece, h, w):
    global ans
    coordinate = None
    for _h in range(m):
        for _w in range(m):
            if piece[_h][_w] != '-1':
                if piece[_h][_w] == picture[h+_h][w+_w]:
                    if coordinate is None:
                        coordinate = (int(w+_w+1), int(h+_h+1))
                else:
                    return
    else:
        if ans is None:
            ans = coordinate
        elif coordinate[1] <= ans[1] and coordinate[0] < ans[0]:
            ans = coordinate
        return True
    
def move(piece, c):
    _piece = []
    for w in range(m):
        lis = []
        for h in range(m):
            lis.append(piece[h][w])
        else:
            lis.reverse()
            _piece.append(lis)
    else:
        main(_piece, c+1)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    picture = [raw_input().split() for i in range(n)]
    piece = [raw_input().split() for i in range(m)]
    ans = None
    main(piece, 1)
    if ans:
        print ans[0], ans[1]
    else:
        print 'NA'

Submission status: Wrong Answer

Solution code:
def main(piece, c):
    for h in range(n-m+1):
        for w in range(n-m+1):
            if f(piece, h, w):
                break
    if c != 4:
        move(piece, c)

def f(piece, h, w):
    global ans
    coordinate = None
    for _h in range(m):
        for _w in range(m):
            if piece[_h][_w] != '-1':
                if piece[_h][_w] == picture[h+_h][w+_w]:
                    if coordinate is None:
                        coordinate = (int(w+_w+1), int(h+_h+1))
                else:
                    return
    else:
        if ans is None:
            ans = coordinate
        elif coordinate[1] < ans[1] and coordinate[0] < ans[0]:
            ans = coordinate
        return True
    
def move(piece, c):
    _piece = []
    for w in range(m):
        lis = []
        for h in range(m):
            lis.append(piece[h][w])
        else:
            lis.reverse()
            _piece.append(lis)
    else:
        main(_piece, c+1)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    picture = [raw_input().split() for i in range(n)]
    piece = [raw_input().split() for i in range(m)]
    ans = None
    main(piece, 1)
    if ans:
        print ans[0], ans[1]
    else:
        print 'NA'

Submission status: Wrong Answer

Solution code:
ans = None
def main(piece, c):
    for h in range(n-m+1):
        for w in range(n-m+1):
            if f(piece, h, w):
                break
    if c != 4:
        move(piece, c)
    else:
        if ans:
            print ans[0], ans[1]
        else:
            print 'NA'

def f(piece, h, w):
    global ans
    coordinate = None
    for _h in range(m):
        for _w in range(m):
            if piece[_h][_w] != '-1':
                if piece[_h][_w] == picture[h+_h][w+_w]:
                    if coordinate is None:
                        coordinate = (int(w+_w+1), int(h+_h+1))
                else:
                    return
    else:
        if ans is None:
            ans = coordinate
        elif coordinate[1] < ans[1]:
            ans = coordinate
        elif coordinate[1] == ans[1]:
            if coordinate[0] < ans[0]:
                ans = coordinate
        return True
    
def move(piece, c):
    _piece = []
    for w in range(m):
        lis = []
        for h in range(m):
            lis.append(piece[h][w])
        else:
            lis.reverse()
            _piece.append(lis)
    else:
        main(_piece, c+1)

while True:
    n, m = map(int, raw_input().split())
    if n == m == 0: break
    picture = [raw_input().split() for i in range(n)]
    piece = [raw_input().split() for i in range(m)]
    main(piece, 1)

Submission status: Wrong Answer

Solution code:
def rotated(pic):
    m = []
    t = zip(*pic[::-1])
    for row in t:
        m.append(row)

    return m


def is_match(window, pic_map, curr_x, curr_y):
    for k, v in pic_map.items():
        if k == 'head':
            continue
        for x, y in v:
            if window[curr_x + x][curr_y + y] != k:
                return False

    return True


def really_pic(pic):
    pic_map = {}
    for i in range(len(pic)):
        for j in range(len(pic[i])):
            if pic[i][j] != -1:
                if not pic_map.get('head'):
                    pic_map['head'] = (i, j)
                if pic_map.get(pic[i][j]):
                    pic_map[pic[i][j]].append((i, j))
                else:
                    pic_map[pic[i][j]] = [(i, j)]

    return pic_map


def start():
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break

        window = []
        pic = []
        for _ in range(m):
            window.append(list(map(int, input().split())))

        for _ in range(n):
            pic.append(list(map(int, input().split())))

        map0 = really_pic(pic)
        pic_rotated90 = rotated(pic)
        map90 = really_pic(pic_rotated90)
        pic_rotated180 = rotated(pic_rotated90)
        map180 = really_pic(pic_rotated180)
        pic_rotated270 = rotated(pic_rotated180)
        map270 = really_pic(pic_rotated270)

        map_rotated = [map0, map90, map180, map270]

        res = algorithm(window, m, n, map_rotated)
        print(res if type(res) == str else str(res[0]) + ' ' + str(res[1]))


def algorithm(window, m, n, map_rotated):
    for map_ro in map_rotated:
        for i in range(m - n + 1):
            for j in range(m - n + 1):
                if is_match(window, map_ro, i, j):
                    return j + map_ro['head'][1] + 1, i + map_ro['head'][0] + 1
    return 'NA'


start()

Submission status: Wrong Answer

Solution code:
def rotated(pic):
    m = []
    t = zip(*pic[::-1])
    for row in t:
        m.append(row)

    return m


def is_match(window, pic_map, curr_x, curr_y):
    for k, v in pic_map.items():
        if k == 'head':
            continue
        for x, y in v:
            if window[curr_x + x][curr_y + y] != k:
                return False

    return True


def really_pic(pic):
    pic_map = {}
    for i in range(len(pic)):
        for j in range(len(pic[i])):
            if pic[i][j] != -1:
                if not pic_map.get('head'):
                    pic_map['head'] = (i, j)
                if pic_map.get(pic[i][j]):
                    pic_map[pic[i][j]].append((i, j))
                else:
                    pic_map[pic[i][j]] = [(i, j)]

    return pic_map


def start():
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break

        window = []
        pic = []
        for _ in range(m):
            window.append(list(map(int, input().split())))

        for _ in range(n):
            pic.append(list(map(int, input().split())))

        map0 = really_pic(pic)
        pic_rotated90 = rotated(pic)
        map90 = really_pic(pic_rotated90)
        pic_rotated180 = rotated(pic_rotated90)
        map180 = really_pic(pic_rotated180)
        pic_rotated270 = rotated(pic_rotated180)
        map270 = really_pic(pic_rotated270)

        map_rotated = [map0, map270, map180, map90]

        res = algorithm(window, m, n, map_rotated)
        print(res if type(res) == str else str(res[0]) + ' ' + str(res[1]))


def algorithm(window, m, n, map_rotated):
    for map_ro in map_rotated:
        for i in range(m - n + 1):
            for j in range(m - n + 1):
                if is_match(window, map_ro, i, j):
                    return j + map_ro['head'][1] + 1, i + map_ro['head'][0] + 1
    return 'NA'


start()

Submission status: Wrong Answer

Solution code:
def rotated(pic):
    m = []
    t = zip(*pic[::-1])
    for row in t:
        m.append(row)

    return m


def is_match(window, pic_map, curr_x, curr_y):
    for k, v in pic_map.items():
        if k == 'head':
            continue
        for x, y in v:
            if window[curr_x + x][curr_y + y] != k:
                return False

    return True


def really_pic(pic):
    pic_map = {}
    for i in range(len(pic)):
        for j in range(len(pic[i])):
            if pic[i][j] != -1:
                if not pic_map.get('head'):
                    pic_map['head'] = (i, j)
                if pic_map.get(pic[i][j]):
                    pic_map[pic[i][j]].append((i, j))
                else:
                    pic_map[pic[i][j]] = [(i, j)]

    return pic_map


def start():
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break

        window = []
        pic = []
        for _ in range(m):
            window.append(list(map(int, input().split())))

        for _ in range(n):
            pic.append(list(map(int, input().split())))

        # print(pic)
        map0 = really_pic(pic)
        pic_rotated90 = rotated(pic)
        # print(pic_rotated90)
        map90 = really_pic(pic_rotated90)
        pic_rotated180 = rotated(pic_rotated90)
        # print(pic_rotated180)
        map180 = really_pic(pic_rotated180)
        pic_rotated270 = rotated(pic_rotated180)
        # print(pic_rotated270)
        map270 = really_pic(pic_rotated270)

        map_rotated = [map0, map90, map180, map270]

        res = algorithm(window, m, n, map_rotated)
        print(res if type(res) == str else str(res[0]) + ' ' + str(res[1]))


def algorithm(window, m, n, map_rotated):
    for map_ro in map_rotated:
        for i in range(m - n + 1):
            for j in range(m - n + 1):
                if is_match(window, map_ro, i, j):
                    return j + map_ro['head'][1] + 1, i + map_ro['head'][0] + 1
    return 'NA'


start()

Submission status: Wrong Answer

Solution code:
""" Created by Jieyi on 9/28/16. """


def rotated(pic):
    return [list(row) for row in zip(*reversed(pic))]


def is_match(window, pic_map, curr_x, curr_y):
    for k, v in pic_map.items():
        if k == 'head':
            continue
        for x, y in v:
            if window[curr_x + x][curr_y + y] != k:
                return False

    return True


def really_pic(pic):
    pic_map = {}
    for i in range(len(pic)):
        for j in range(len(pic[i])):
            if pic[i][j] != -1:
                if not pic_map.get('head'):
                    pic_map['head'] = (i, j)
                if pic_map.get(pic[i][j]):
                    pic_map[pic[i][j]].append((i, j))
                else:
                    pic_map[pic[i][j]] = [(i, j)]

    return pic_map


def start():
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break

        window = [list(map(int, input().split())) for _ in range(m)]
        pic = [list(map(int, input().split())) for _ in range(n)]

        # print(pic)
        map0 = really_pic(pic)
        pic_rotated90 = rotated(pic)
        # print(pic_rotated90)
        map90 = really_pic(pic_rotated90)
        pic_rotated180 = rotated(pic_rotated90)
        # print(pic_rotated180)
        map180 = really_pic(pic_rotated180)
        pic_rotated270 = rotated(pic_rotated180)
        # print(pic_rotated270)
        map270 = really_pic(pic_rotated270)

        map_rotated = [map0, map90, map180, map270]

        res = algorithm(window, m, n, map_rotated)
        print(res if type(res) == str else str(res[0]) + ' ' + str(res[1]))


def algorithm(window, m, n, map_rotated):
    for map_ro in map_rotated:
        for i in range(m - n + 1):
            for j in range(m - n + 1):
                if is_match(window, map_ro, i, j):
                    return j + map_ro['head'][1] + 1, i + map_ro['head'][0] + 1
    return 'NA'


def main():
    start()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
""" Created by Jieyi on 10/9/16. """
import io
import sys

# Simulate the redirect stdin.
if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def print_map(window):
    for i in range(len(window)):
        print(window[i])


def rotated(pic):
    return [list(row) for row in zip(*reversed(pic))]


def input_source():
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break

        window = [list(map(int, input().split())) for _ in range(m)]
        pic = [list(map(int, input().split())) for _ in range(n)]

        res = algorithm(m, n, window, pic)
        print(res if type(res) == str else str(res[0]) + ' ' + str(res[1]))


def match(start_x, start_y, window, fragment):
    for i in range(len(fragment)):
        for j in range(len(fragment[i])):
            if fragment[i][j] == -1:
                continue
            if fragment[i][j] != window[start_x + i][start_y + j]:
                return False
    return True


def algorithm(m, n, window, fragment):
    origin = fragment
    rotated_270 = rotated(origin)
    rotated_180 = rotated(rotated_270)
    rotated_90 = rotated(rotated_180)

    array = [origin, rotated_270, rotated_180, rotated_90]

    for pic in array:
        for i in range(m - n + 1):
            for j in range(m - n + 1):
                if match(i, j, window, pic):
                    for k in range(len(pic)):
                        for v in range(len(pic[k])):
                            if pic[k][v] != -1:
                                return j + v + 1, i + k + 1
    return 'NA'


def main():
    input_source()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
""" Created by Jieyi on 10/9/16. """
import io
import sys

# Simulate the redirect stdin.
if len(sys.argv) > 1:
    filename = sys.argv[1]
    inp = ''.join(open(filename, "r").readlines())
    sys.stdin = io.StringIO(inp)


def print_map(window):
    for i in range(len(window)):
        print(window[i])


def rotated(pic):
    return [list(row) for row in zip(*reversed(pic))]


def input_source():
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break

        window = [list(map(int, input().split())) for _ in range(m)]
        pic = [list(map(int, input().split())) for _ in range(n)]

        res = algorithm(m, n, window, pic)
        print(res if type(res) == str else str(res[0]) + ' ' + str(res[1]))


def match(start_x, start_y, window, fragment):
    for h in range(len(fragment)):
        for w in range(len(fragment[h])):
            if fragment[h][w] == -1:
                continue
            if fragment[h][w] != window[start_x + h][start_y + w]:
                return False
    return True


def algorithm(m, n, window, fragment):
    origin = fragment
    rotated_270 = rotated(origin)
    rotated_180 = rotated(rotated_270)
    rotated_90 = rotated(rotated_180)

    array = [origin, rotated_90, rotated_180, rotated_270]

    for pic in array:
        for h in range(m - n + 1):
            for w in range(m - n + 1):
                if match(h, w, window, pic):
                    for h_p in range(len(pic)):
                        for w_p in range(len(pic[h_p])):
                            if pic[h_p][w_p] != -1:
                                return w + w_p + 1, h + h_p + 1
    return 'NA'


def main():
    input_source()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def rotate90(L,m):
    P=[[-1]*m for i in range(m)]
    for i in range(m)[::-1]:
        for j in range(m):
            P[m-i-1][j]=L[j][i]
    return P

def Judge(y,x):
    for i in range(m):
        for j in range(m):
            if pic[i][j]!=-1:
                if scene[y+i][x+j]!=pic[i][j]:
                    return False
    return True

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    scene=[map(int,raw_input().split()) for i in range(n)]
    pic=[map(int,raw_input().split()) for i in range(m)]
    ans=[]
    for k in range(4):
        t=[i for i in range(m) if pic[0][i]!=-1][0]
        for i in range(n-m):
            for j in range(n-m):
                if Judge(i,j):
                    ans.append((j+1,i+t+1))
        pic=rotate90(pic,m)
    ans.sort()
    print "%d %d"%(ans[0][1],ans[0][0]) if len(ans)!=0 else "NA"

Submission status: Wrong Answer

Solution code:
def rotate90(L,m):
    P=[[-1]*m for i in range(m)]
    for i in range(m)[::-1]:
        for j in range(m):
            P[m-i-1][j]=L[j][i]
    return P

def Judge(y,x):
    for i in range(m):
        for j in range(m):
            if pic[i][j]!=-1:
                if scene[y+i][x+j]!=pic[i][j]:
                    return False
    return True

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    scene=[map(int,raw_input().split()) for i in range(n)]
    pic=[map(int,raw_input().split()) for i in range(m)]
    ans=[]
    for k in range(4):
        t=[i for i in range(m) if pic[0][i]!=-1][0]
        for i in range(n-m+1):
            for j in range(n-m+1):
                if Judge(i,j):
                    ans.append((j+1,i+t+1))
        pic=rotate90(pic,m)
    ans.sort()
    print "%d %d"%(ans[0][1],ans[0][0]) if len(ans)!=0 else "NA"

Submission status: Wrong Answer

Solution code:
def rotate90(L,m):
    P=[[-1]*m for i in range(m)]
    for i in range(m)[::-1]:
        for j in range(m):
            P[m-i-1][j]=L[j][i]
    return P

def Judge(y,x):
    for i in range(m):
        for j in range(m):
            if pic[i][j]!=-1:
                if scene[y+i][x+j]!=pic[i][j]:
                    return False
    return True

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    scene=[map(int,raw_input().split()) for i in range(n)]
    pic=[map(int,raw_input().split()) for i in range(m)]
    ans=[]
    for k in range(3):
        t=[i for i in range(m) if pic[0][i]!=-1][0]
        for i in range(n-m+1):
            for j in range(n-m+1):
                if Judge(i,j):
                    ans.append((j+1,i+t+1))
        pic=rotate90(pic,m)
    ans.sort()
    print "%d %d"%(ans[0][1],ans[0][0]) if len(ans)!=0 else "NA"

Submission status: Wrong Answer

Solution code:
def rotate90(L,m):
    P=[[-1]*m for i in range(m)]
    for i in range(m)[::-1]:
        for j in range(m):
            P[m-i-1][j]=L[j][i]
    return P

def Judge(y,x):
    for i in range(m):
        for j in range(m):
            if pic[i][j]!=-1:
                if scene[y+i][x+j]!=pic[i][j]:
                    return False
    return True

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    scene=[map(int,raw_input().split()) for i in range(n)]
    pic=[map(int,raw_input().split()) for i in range(m)]
    ans=[]
    for k in range(4):
        t=[i for i in range(m) if pic[0][i]!=-1][0]
        for i in range(n-m+1):
            for j in range(n-m+1):
                if Judge(i,j):
                    ans.append((i+t+1,j+1))
        pic=rotate90(pic,m)
    ans.sort()
    print "%d %d"%(ans[0][0],ans[0][1]) if len(ans)!=0 else "NA"

Submission status: Wrong Answer

Solution code:
def rotate90(L,m):
    temp=[[-1]*m for i in range(m)]
    for y in range(m):
        for x in range(m):
            temp[x][y]=L[x][y]
    for	y in range(m):
	for x in range(m):
            L[y][m-x-1]=temp[x][y]
    return L

def Judge(y,x):
    for i in range(m):
        for j in range(m):
            if pic[i][j]!=-1:
                if scene[y+i][x+j]!=pic[i][j]:
                    return False
    return True

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    scene=[map(int,raw_input().split()) for i in range(n)]
    pic=[map(int,raw_input().split()) for i in range(m)]
    ans=[]
    for k in range(4):
        t=[i for i in range(m) if pic[0][i]!=-1][0]
        for i in range(n-m+1):
            for j in range(n-m+1):
                if Judge(i,j):
                    ans.append((i+t+1,j+1))
        pic=rotate90(pic,m)
    ans.sort()
    print "%d %d"%(ans[0][0],ans[0][1]) if len(ans)!=0 else "NA"

Submission status: Wrong Answer

Solution code:
def getxy(pic,x,y):
	flag = 0
	for dy in range(m):
		for dx in range(m):
			if pic[dy][dx] > -1:
				ans = str(x+dx+1)+" "+str(y+dy+1)
				flag = 1
				break
		if flag == 1: break
	return ans

# try-except is necessary
while 1:
	try:
		n,m = map(int,raw_input().split())
		if n == 0: break
		scene = [map(int,raw_input().split()) for i in range(n)]
		pic = [map(int,raw_input().split()) for i in range(m)]
		ans = "NA"
		for rot in range(4):
			if scene == pic:
				ans = getxy(pic,0,0)
			for y in range(n-m):
				for x in range(n-m):
					flag = 0
					for dy in range(m):
						for dx in range(m):
							if pic[dy][dx] > -1 and scene[y+dy][x+dx] - pic[dy][dx] != 0:
								flag = 1
								break
						if flag == 1: break
					if flag == 0:
						ans = getxy(pic,x,y)
				if flag == 0: break
			if flag == 0: break
			pic = [[pic[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
		print ans
	except:
		pass

Submission status: Wrong Answer

Solution code:
def getxy(pic,x,y,ans):
	flag = 0
	for dy in range(m):
		for dx in range(m):
			if pic[dy][dx] > -1:
				xy = [x+dx+1,y+dy+1]
				flag = 1
				break
		if flag == 1: break
	if ans == "NA" or xy[1] < ans[1] or (xy[1] == ans[1] and xy[0] < ans[0]):
		return xy
	else:
		return ans

# try-except is necessary
while 1:
	try:
		n,m = map(int,raw_input().split())
		if n == 0: break
		scene = [map(int,raw_input().split()) for i in range(n)]
		pic = [map(int,raw_input().split()) for i in range(m)]
		ans = "NA"
		for rot in range(4):
			if scene == pic:
				ans = getxy(pic,0,0,ans)
			for y in range(n-m):
				for x in range(n-m):
					flag = 0
					for dy in range(m):
						for dx in range(m):
							if pic[dy][dx] > -1 and scene[y+dy][x+dx] - pic[dy][dx] != 0:
								flag = 1
								break
						if flag == 1: break
					if flag == 0:
						ans = getxy(pic,x,y,ans)
				if flag == 0: break
			pic = [[pic[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
		print ans if ans == "NA" else " ".join(map(str,ans))
	except:
		pass

Submission status: Wrong Answer

Solution code:
def getxy(pic,x,y,ans):
	for dy in range(m):
		for dx in range(m):
			if pic[dy][dx] > -1:
				xy = [x+dx+1,y+dy+1]
				if ans == "NA" or xy[1] < ans[1] or (xy[1] == ans[1] and xy[0] < ans[0]):
					return xy
				else:
					return ans

# try-except is necessary
while 1:
	try:
		n,m = map(int,raw_input().split())
		if n == 0: break
		scene = [map(int,raw_input().split()) for i in range(n)]
		pic = [map(int,raw_input().split()) for i in range(m)]

		ans = "NA"
		for rot in range(4):
			if scene == pic:
				ans = getxy(pic,0,0,ans)
			for y in range(n-m):
				for x in range(n-m):
					flag = 0
					for dy in range(m):
						for dx in range(m):
							if pic[dy][dx] > -1 and scene[y+dy][x+dx] - pic[dy][dx] != 0:
								flag = 1
								break
						if flag == 1: break
					if flag == 0:
						ans = getxy(pic,x,y,ans)
						break
				if flag == 0: break
			pic = [[pic[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
		print ans if ans == "NA" else " ".join(map(str,ans))
	except:
		pass

Submission status: Wrong Answer

Solution code:
def getxy(P,x,y,ans):
	for dy in range(m):
		for dx in range(m):
			if P[dy][dx] > -1:
				xy = [x+dx+1,y+dy+1]
				if xy[1] < ans[1] or (xy[1] == ans[1] and xy[0] < ans[0]):
					return xy
				else:
					return ans

# try-except is necessary
while 1:
	try:
		n,m = map(int,raw_input().split())
		if n == 0: break
		S = [map(int,raw_input().split()) for i in range(n)]
		P = [map(int,raw_input().split()) for i in range(m)]
		ans = [n+1,n+1]
		for rot in range(4):
			for y in range(min(ans[1],n-m+1)):
				for x in range(min(ans[1],n-m+1)):
					flag = 0
					for dy in range(m):
						for dx in range(m):
							if P[dy][dx] > -1 and S[y+dy][x+dx] - P[dy][dx] != 0:
								flag = 1
								break
						if flag == 1: break
					if flag == 0:
						ans = getxy(P,x,y,ans)
						break
				if flag == 0: break
			P = [[P[j][i] for j in range(m-1,-1,-1)] for i in range(m)]
		print "NA" if ans == [n+1,n+1] else " ".join(map(str,ans))
	except:
		pass

Submission status: Time Limit Exceeded

Solution code:
def rotate(pic, m):
    tmp = [[0] * m for i in range(m)]
    for i in range(m):
        for j in range(m):
            tmp[i][j] = pic[m-j-1][i]
    for i in range(m):
        for j in range(m):
            pic[i][j] = tmp[i][j]

def searchPoints(p, w, n, m, px, py):
    space = 0
    for i in range(m):
        if p[0][i] == -1:
            space += 1
        else:
            break
    for i in range(n-m+1):
        for j in range(n-m+1):
            flag = True
            for k in range(m):
                for l in range(m):
                    if p[k][l] == -1: continue
                    if p[k][l] != w[i+k][l+j]:
                        flag = False
            if flag:
                if i < py or (i == py and j + space < px):
                    px = j + space
                    py = i
    return px, py

while True:
    f = lambda:map(int, raw_input().split())
    n, m = f()
    if n == m == 0: break
    win = [f() for i in range(n)]
    pic = [f() for i in range(m)]
    INFTY = 1000
    px = INFTY
    py = INFTY
    for i in range(4):
        px, py = searchPoints(pic, win, n, m, px, py)
        rotate(pic, m)
    print 'NA' if px == py == INFTY else "%d %d"%(px+1, py+1)

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline


from itertools import product
from operator import itemgetter
from math import isinf


def scrap_top_left(picture):
    for py, px in product(range(len(picture)), repeat=2):
        if picture[py][px] != -1:
            return px, py


def is_match(window, picture, wx, wy):
    for py, px in product(range(len(picture)), repeat=2):
        if picture[py][px] == -1:
            continue
        if window[wy + py][wx + px] != picture[py][px]:
            return False
    return True


def search(window, picture):
    for wy, wx in product(range(len(window) - len(picture) + 1), repeat=2):
        if is_match(window, picture, wx, wy):
            px, py = scrap_top_left(picture)
            return wx + px + 1, wy + py + 1
    return float('inf'), float('inf')


# http://d.hatena.ne.jp/odz/20070622/1182497414
def rotate_clockwise(matrix):
    return [list(row) for row in zip(*reversed(matrix))]


while True:
    window_size, picture_size = map(int, readline().split())
    if window_size == 0:
        break
    window = [list(map(int, readline().split())) for _ in range(window_size)]
    picture = [list(map(int, readline().split())) for _ in range(picture_size)]
    top_left = []
    for _ in range(4):
        top_left.append(search(window, picture))
        picture = rotate_clockwise(picture)
    top_left = min(top_left, key=itemgetter(1, 0))
    if isinf(top_left[0]):
        print('NA')
    else:
        print(*top_left)