Arkady is playing Battleship. The rules of this game aren't really important.

There is a field of $n \times n$ cells. There should be exactly one $k$-decker on the field, i. e. a ship that is $k$ cells long oriented either horizontally or vertically. However, Arkady doesn't know where it is located. For each cell Arkady knows if it is definitely empty or can contain a part of the ship.

Consider all possible locations of the ship. Find such a cell that belongs to the maximum possible number of different locations of the ship.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the size of the field and the size of the ship.

The next $n$ lines contain the field. Each line contains $n$ characters, each of which is either '#' (denotes a definitely empty cell) or '.' (denotes a cell that can belong to the ship).


-----Output-----

Output two integers — the row and the column of a cell that belongs to the maximum possible number of different locations of the ship.

If there are multiple answers, output any of them. In particular, if no ship can be placed on the field, you can output any cell.


-----Examples-----
Input
4 3
#..#
#.#.
....
.###

Output
3 2

Input
10 4
#....##...
.#...#....
..#..#..#.
...#.#....
.#..##.#..
.....#...#
...#.##...
.#...#.#..
.....#..#.
...#.#...#

Output
6 1

Input
19 6
##..............###
#......#####.....##
.....#########.....
....###########....
...#############...
..###############..
.#################.
.#################.
.#################.
.#################.
#####....##....####
####............###
####............###
#####...####...####
.#####..####..#####
...###........###..
....###########....
.........##........
#.................#

Output
1 8



-----Note-----

The picture below shows the three possible locations of the ship that contain the cell $(3, 2)$ in the first sample. [Image]

Difficulty: interview

Starter code:

Solutions:
import sys
import math

n, k = list(map(int,sys.stdin.readline().strip().split(' ')))
grid = []
for n0 in range(n):
	grid.append([char for char in sys.stdin.readline().strip()])

res = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
	for j in range(n):
		if grid[i][j] == '#':
			continue
		ii, jj = i,j

		cpt = 0
		while ii < n and cpt < k:
			if grid[ii][j] == '#':
				break
			else:
				cpt += 1
			ii += 1
		if cpt == k:
			for ii in range(i,i+k):
				res[ii][j] += 1

		cpt = 0
		while jj < n and cpt < k:
			if grid[i][jj] == '#':
				break
			else:
				cpt += 1
			jj += 1
		if cpt == k:
			for jj in range(j,j+k):
				res[i][jj] += 1
ans = [0,0]
maxsf = -1
for i in range(n):
	for j in range(n):
		if res[i][j] > maxsf:
			ans = [i,j]
			maxsf = res[i][j]
print(ans[0]+1, ans[1]+1)









n,k = map(int,input().split())
mapp = [list(input()) for i in range(n)]
res = 0
res = [[0 for i in range(n)] for j in range(n)] 
for i in range(n):
    count = 0
    for j in range(n):
        if (mapp[i][j] == '.'):
            count += 1
        else:
            count = 0
        if (count >= k):
            for t in range(j - k + 1,j + 1):
                res[i][t] += 1

for i in range(n):
    count = 0
    for j in range(n):
        if (mapp[j][i] == '.'):
            count += 1
        else:
            count = 0
        if (count >= k):
            for t in range(j - k + 1,j + 1):
                res[t][i] += 1
ress = [0,0]
maxx = -1
for i in range(n):
    for j in range(n):
        if (maxx < res[i][j]):
            maxx = res[i][j]
            ress[0],ress[1] = i + 1,j + 1
print(*ress)

n, k = list(map(int, input().split()))
m = [list(input()) for _ in range(n)]
p = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        s = True
        if i + k - 1 < n:
            for l in range(k):
                if m[i + l][j] != '.':
                    s = False
                    break
            if s:
                for l in range(k):
                    p[i + l][j] += 1

        s = True
        if j + k - 1 < n:
            for l in range(k):
                if m[i][j + l] != '.':
                    s = False
                    break
            if s:
                for l in range(k):
                    p[i][j + l] += 1

mx = -1
for i in range(n):
    for j in range(n):
        if p[i][j] > mx:
            ans = (i + 1, j + 1)
            mx = p[i][j]

print(*ans)


n, k = list(map(int, input().split()))
field = [input() for i in range(n)]
field_ = [''.join([field[i][j] for i in range(n)]) for j in range(n)]

for_ans = [[0] * n for i in range(n)]
for_s = '.' * k

for i, el in enumerate(field):
    for j in range(n - k + 1):
        if el[j: j + k] == for_s:
            for j_ in range(j, j + k):
                for_ans[i][j_] += 1

for i, el in enumerate(field_):
    for j in range(n - k + 1):
        if el[j: j + k] == for_s:
            for j_ in range(j, j + k):
                for_ans[j_][i] += 1

ans = 0
x, y = 1, 1

for i in range(n):
    for j in range(n):
        if for_ans[i][j] > ans:
            ans = for_ans[i][j]
            x = i + 1
            y = j + 1

print(x, y)


n, k = list(map(int, input().split()))
matrix = []
for i in range(n):
    matrix.append(list(input()))
spree = 0
counts = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if matrix[i][j] == '#':
            spree = 0
        else:
            spree += 1
            if spree == k:
                for z in range(j-k+1, j+1):
                    counts[i][z] += 1
                spree = k-1
    spree = 0
for i in range(n):
    for j in range(n):
        if matrix[j][i] == '#':
            spree = 0
        else:
            spree += 1
            if spree == k:
                for z in range(j-k+1, j+1):
                    counts[z][i] += 1
                spree = k-1
    spree = 0
ans1, ans2 = 0, 0
for i in range(n):
    for j in range(n):
        if counts[i][j] > counts[ans1][ans2]:
            ans1 = i
            ans2 = j
print("{} {}".format(ans1 + 1, ans2 + 1))


def make():
    s = ''
    for x in range(j, j + k):
        s += field[x][i]
    return s

n, k = map(int, input().split())
field = []
for i in range(n):
    field.append(input())
best = []
for i in range(n):
    best.append([0] * n)
for i in range(n):
    for j in range(n - k + 1):
        if field[i][j: j + k] == '.' * k:
            for x in range(j, j + k):
                best[i][x] += 1
for i in range(n):
    for j in range(n - k + 1):
        s = make()
        if s == '.' * k:
            for x in range(j, j + k):
                best[x][i] += 1
ind1 = 0
ind2 = 0
ans = -19942347392
for i in range(n):
    for j in range(n):
        if best[i][j] > ans:
            ans = best[i][j]
            ind1 = i
            ind2 = j
if ans > 0:
    print(ind1 + 1, ind2 + 1)
else:
    print(1, 1)

n, k = [int(i) for i in input().split(' ')]
grid = [input() for i in range(n)]

grid_score = [[0 for i in range(n)] for j in range(n)]

for row in range(n):
    for col in range(n - k + 1):
        if all(['.' == grid[row][col + x] for x in range(k)]):
            for x in range(k):
                grid_score[row][col + x] += 1

for row in range(n - k + 1):
    for col in range(n):
        if all(['.' == grid[row + x][col] for x in range(k)]):
            for x in range(k):
                grid_score[row + x][col] += 1

max_score = 0
max_row = 0
max_col = 0
for row in range(n):
    for col in range(n):
        if grid_score[row][col] > max_score:
            max_score = grid_score[row][col]
            max_row = row
            max_col = col

print(max_row + 1, max_col + 1)


from pprint import pprint

# if __main__ == ''

N, K = (int(i) for i in input().split())


field = []

count = [[0] * N for i in range(N)]

for i in range(N):
    field.append([c == '.' for c in input()])


for i in range(N):
    for j in range(N):
        # for k in range(K):
        #     print(field[i + k][j])
        if i + K <= N:
            if all(field[i + k][j] for k in range(K)):
                for k in range(K):
                    count[i + k][j] += 1
        if K > 1 and j + K <= N:
            # for k in range(K):
            #     print(field[i][j + k])
            if all(field[i][j + k] for k in range(K)):
                for k in range(K):
                    count[i][j + k] += 1

# print('\n'.join(''.join(str(x) for x in y) for y in count))
# print('\n'.join(''.join('.' if x else '#' for x in y) for y in field))

M = max(max(i) for i in count)

for i in range(N):
    for j in range(N):
        if count[i][j] == M:
            print(i + 1, j + 1)
            return

print(0, 0)


n, k = list(map(int, input().split(" ")))

rows = []
for i in range(n):
    rows +=  [ input() ] 

cnt = [[0 for i in range(n) ] for j in range(n)]

for i in range(n):
    for j in range(n):
        flag = True
        for kk in range(k):
            if j + kk > n - 1 or  rows[i][j + kk] == '#':
                flag = False
                break
        if flag:
            for kk in range(k):
                cnt[i][j + kk] += 1
        flag = True
        for kk in range(k):
            if i + kk > n - 1 or rows[i + kk][j] == '#':
                flag = False
                break
        if flag:
            for kk in range(k):
                cnt[i + kk][j] += 1
         
mx = 0
ia = 0
ij = 0
for i in range(n):
    for j in range(n):
        if cnt[i][j] > mx:
            mx = cnt[i][j]
            ia = i
            ij = j

print(ia + 1, ij + 1)


n,k=list(map(int,input().split()))
L=[]
for i in range(n):
    L.append(input())

ps1=[[0]*(n+1) for i in range(n)]  #number of "#"
ps2=[[0]*n for i in range(n+1)]
for i in range(n):
    for j in range(n):
        ps1[i][j+1]=ps1[i][j]+int(L[i][j]=="#")
        ps2[i+1][j]=ps2[i][j]+int(L[i][j]=="#")

T=[[0]*n for i in range(n)]
for i in range(n):
    for j in range(n-k+1):
        if ps1[i][j+k]-ps1[i][j]==0:
            for x in range(k):
                T[i][j+x]+=1
for i in range(n-k+1):
    for j in range(n):
        if ps2[i+k][j]-ps2[i][j]==0:
            for x in range(k):
                T[i+x][j]+=1

ans1,ans2=0,0
for i in range(n):
    for j in range(n):
        if T[i][j]>T[ans1][ans2]:
            ans1,ans2=i,j
print(ans1+1,ans2+1)
        
        





from collections import Counter


def read_nums():
    return [int(x) for x in input().split()]


def read_board(n):
    board = []
    for _ in range(n):
        board.append(input())
    return board


def check_horizontal(board, boat_size, col_index, row_index):
    for i in range(col_index, col_index + boat_size):
        if i >= len(board):
            return False
        if board[row_index][i] == '#':
            return False
    return True


def check_vertical(board, boat_size, col_index, row_index):
    for i in range(row_index, row_index + boat_size):
        if i >= len(board):
            return False
        if board[i][col_index] == '#':
            return False
    return True


def main():
    n, k = read_nums()
    board = read_board(n)
    counter = Counter()
    for row_index in range(n):
        for col_index in range(n):
            if check_horizontal(board, k, col_index, row_index):
                for i in range(col_index, col_index + k):
                    counter[(row_index, i)] += 1
            if check_vertical(board, k, col_index, row_index):
                for i in range(row_index, row_index + k):
                    counter[(i, col_index)] += 1
    res = (0, 0)
    for k, v in list(counter.items()):
        if v > counter[res]:
            res = k

    print(res[0] + 1, res[1] + 1)


def __starting_point():
    main()

__starting_point()

n,k=map(int,input().split(' '))
l=[]
l1=[]
for i in range(0,n):
    s=input()
    l.append(s)
    l1.append(n*[0])
a1=1
a2=1
maxx=0
for i in range(0,n):
    for j in range(0,n-k+1):
        if (l[i])[j:j+k]==k*".":
            for m in range(0,k):
                l1[i][j+m]+=1
                if l1[i][j+m]>maxx:
                    maxx=l1[i][j+m]
                    a1=i+1
                    a2=j+m+1
l2=[]
for i in range(0,n):
    s=""
    for j in range(0,n):
        s+=l[j][i]
    l2.append(s)
for i in range(0,n):
    for j in range(0,n-k+1):
        if (l2[i])[j:j+k]==k*".":
            for m in range(0,k):
                l1[j+m][i]+=1
                if l1[j+m][i]>maxx:
                    maxx=l1[j+m][i]
                    a1=j+m+1
                    a2=i+1
print(a1,a2)

n, k = map(int, input().split())
board = []

for _ in range(n):
    board.append(input())

result = [None] * n

for i in range(n):
    result[i] = [0] * n

# horizontally
for r, row in enumerate(board):
    for i in range(len(board) - k + 1):
        if row[i:i+k] == '.' * k:
            for x in range(i, i + k):
                result[r][x] += 1

# print("\n".join(map(str, result)))

# vertically
for col in range(len(board)):
    for i in range(len(board) - k + 1):
        if ''.join([board[j][col] for j in range(i, i + k)]) == '.' * k:
            for x in range(i, i + k):
                result[x][col] += 1

# print("\n".join(map(str, result)))

# find max
_max = 0
max_pos = (0, 0)

for r, row in enumerate(result):
    for c, col in enumerate(row):
        if col > _max:
            max_pos = (r, c)
            _max = col

print("{} {}".format(max_pos[0] + 1, max_pos[1] + 1))

n,k = [ int(a) for a in input().split() ]

field = []
for i in range(n):
    field.append(input())

poss = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n-k+1):
        good = True
        for ell in range(k):
            if field[j+ell][i] == '#':
                good = False
        if good:
            for ell in range(k):
                poss[j+ell][i] += 1

        good = True
        for ell in range(k):
            if field[i][j+ell] == '#':
                good = False
        if good:
            for ell in range(k):
                poss[i][j+ell] += 1

best = 0
besti = 0
bestj = 0
for i in range(n):
    for j in range(n):
        if best < poss[i][j]:
            best = poss[i][j]
            besti = i
            bestj = j

print(besti+1,bestj+1)



n=input().split()
r=int(n[0])
k=int(n[1])
l=[]
for i in range(r):
    li=input()
    l.append(li)
rl=[]
for i in range(r):
    x=[]
    for j in range(r):
        x.append(0)
    rl.append(x)
for i in range(r):
    for j in range(len(l[i])):
        flag=0
        f=0
        if j+k<=r:
            for q in range(k):
                if l[i][j+q:j+q+1]=='.':
                    continue
                else:
                    flag=1
                    break
            if flag==0:
                for q in range(k):
                    rl[i][j+q]=rl[i][j+q]+1
            if flag==1:
                j=q+1
for i in range(r):
    for j in range(r):
        flag=0
        f=0
        if j+k<=r:
            for q in range(k):
                if l[j+q][i:i+1]=='.':
                    continue
                else:
                    flag=1
                    break
            if flag==0:
                for q in range(k):
                    rl[j+q][i]=rl[j+q][i]+1
            if flag==1:
                j=q+1
maxi=0
maxj=0
m=0
for i in range(r):
    for j in range(r):
        if rl[i][j]>m:
            m=rl[i][j]
            maxi=i
            maxj=j
print(maxi+1,maxj+1)


def read():
    return list(map(int,input().split()))
n,k=read()
a=[]
w=0
q=[]
for i in range(n):
    q.append(w)
b=[]
for i in range(n):
    b.append(q.copy())
for i in range(n):
    a.append(input())
'''if k==1:
    ans=0
    for i in range(n):
        for j in range(n):
            if a[i][j]=='.':
                ans+=1
    print(ans)
    return'''
for i in range(n):
    for j in range(n-k+1):
        for l in range(j,j+k):
            if a[i][l]=='#':
                break
        else:
            for l in range(j,j+k):
                b[i][l]+=1
for i in range(n):
    for j in range(n-k+1):
        for l in range(j,j+k):
            if a[l][i]=='#':
                break
        else:
            for l in range(j,j+k):
                b[l][i]+=1
m=0
ai=1
aj=1
for i in range(n):
    for j in range(n):
        if b[i][j]>m:
            m=b[i][j]
            ai=i+1
            aj=j+1
print(ai,aj)


#This code sucks, you know it and I know it.  
#Move on and call me an idiot later.

n, k = list(map(int, input().split()))
l = [input() for i in range(n)]
d = [[0 for i in range(n)] for i in range(n)]
s = '.' * k
md = 0
for i in range(n):
    for j in range(n):
        if l[i][j:j+k] == s:
            for ii in range(k):
                d[i][j + ii] += 1

for i in range(n):
    for j in range(n):
        if l[j][i] == '.' and j + k <= n:
            jj = j
            while(jj < j + k):
                if l[jj][i] == '.':
                    d[jj][i] += 1
                else:
                    jj -= 1
                    while(jj >= j):
                        d[jj][i] -= 1
                        jj -= 1
                    break
                
                jj += 1

md = max(list(map(max, d)))
for i in range(n):
    for j in range(n):
        if d[i][j] == md:
            print(i+1, j+1)
            return


n, k = list(map(int, input().split()))
f = [list(input()) for _ in range(n)]

ans = (1, 1)
r = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if f[i][j] == '#':
            r[i][j] = 0
        elif i == 0:
            r[i][j] = 1
        else:
            r[i][j] = r[i - 1][j] + 1
c = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if f[i][j] == '#':
            c[i][j] = 0
        elif j == 0:
            c[i][j] = 1
        else:
            c[i][j] = c[i][j - 1] + 1

s = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        for l in range(k):
            if i + l < n and k <= r[i + l][j]:
                s[i][j] += 1
            if j + l < n and k <= c[i][j + l]:
                s[i][j] += 1
        if s[ans[0] - 1][ans[1] - 1] < s[i][j]:
            ans = (i + 1, j + 1)
print(' '.join(map(str, ans)))


def main():
    n, k = [int(x) for x in input().split()]
    board = []
    count = [[0 for i in range(n)] for j in range(n)]
    m, x, y = 0,0,0

    for i in range(n):
        board.append(input())

    for i in range(n):
        for j in range(n):
            if board[i][j] == '.':
                if j+k-1 < n and board[i][j+k-1] == '.':
                    for l in range(j, j+k):
                        if board[i][l] == '#':
                            break
                    else:
                        for l in range(j, j+k):
                            count[i][l] += 1

                if i+k-1 < n and board[i+k-1][j] == '.':
                    for l in range(i, i+k):
                        if board[l][j] == '#':
                            break
                    else:
                        for l in range(i, i+k):
                            count[l][j] += 1
            if count[i][j] > m:
                m = count[i][j]
                x, y = i, j

    print(x+1, y+1)

def __starting_point():
    main()

__starting_point()