Карта звёздного неба представляет собой прямоугольное поле, состоящее из n строк по m символов в каждой строке. Каждый символ — это либо «.» (означает пустой участок неба), либо «*» (означает то, что в этом месте на небе есть звезда). 

Новое издание карты звёздного неба будет напечатано на квадратных листах, поэтому требуется найти минимально возможную сторону квадрата, в который могут поместиться все звезды. Границы искомого квадрата должны быть параллельны сторонам заданного прямоугольного поля.


-----Входные данные-----

В первой строке входных данных записаны два числа n и m (1 ≤ n, m ≤ 1000) — количество строк и столбцов на карте звездного неба.

В следующих n строках задано по m символов. Каждый символ — это либо «.» (пустой участок неба), либо «*» (звезда).

Гарантируется, что на небе есть хотя бы одна звезда.


-----Выходные данные-----

Выведите одно число — минимально возможную сторону квадрата, которым можно накрыть все звезды.


-----Примеры-----
Входные данные
4 4
....
..*.
...*
..**

Выходные данные
3

Входные данные
1 3
*.*

Выходные данные
3

Входные данные
2 1
.
*

Выходные данные
1



-----Примечание-----

Один из возможных ответов на первый тестовый пример:

 [Image] 

Один из возможных ответов на второй тестовый пример (обратите внимание, что покрывающий квадрат выходит за пределы карты звездного неба):

 [Image] 

Ответ на третий тестовый пример:

 [Image]

Difficulty: interview

Starter code:

Solutions:
n, m = input().split()
n = int(n)
m = int(m)
a = []
N = n
for i in range(n) :
    a.append(input().split())
    
for i in range(n) :
    if a[i][0].find('*') == -1 :
        n-=1
    else :
        break
if n != 1 :
    for i in range(len(a)-1,-1,-1) :
        if a[i][0].find('*') == -1 :
            n-=1
        else :
            break
#print(n)

M = m
br = 0
for i in range(m) :
    count = 0
    for j in range(len(a)) :
        if a[j][0][i] != ('*') :
            count+=1
        else :
            br = 1
            break
    if br == 1 :
        break
    if count == N :
        m-=1
br = 0
if m != 1 :
    for i in range(M-1,-1,-1) :
        count = 0
        for j in range(len(a)) :
            if a[j][0][i] != ('*') :
                count+=1
            else :
                br = 1
                break
        if br == 1 :
            break
        if count == N :
            m-=1
#print(m)
if m > n :
    print(m)
else :
    print(n)


from sys import stdin, stdout

def main():
    h, w = map(int, stdin.readline().split())
    ver = set()
    hor = set()
    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            if s[j] == '*':
                hor.add(j)
                ver.add(i)
    stdout.write(str(max(max(hor) - min(hor), max(ver) - min(ver)) + 1))


main()

n, m = map(int, input().split())
l = [n, m]
r = [-1, -1]
for i in range(n):
    A = input()
    if A.find('*')!=-1:
        if i < l[0]:
            l[0] = i
        if A.find('*') < l[1]:
            l[1] = A.find('*')
        if i > r[0]:
            r[0] = i
        if A.rfind('*') > r[1]:
            r[1] = A.rfind('*')
print(max(r[0]-l[0]+1, r[1]-l[1]+1))

def main():
    n, m = list(map(int, input().split()))
    x1, y1, x2, y2 = n, m, -1, -1
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == '*':
                x1, y1 = min(i, x1), min(j, y1)
                x2, y2 = max(i, x2), max(j, y2)
    ans = max(x2 - x1, y2 - y1) + 1
    print(ans)
main()


n,m = map(int,input().split())
a = []
for i in range(n):
    a.append(list(input()))
minj,maxi,maxj,mini = 10000000000000,0,-1,1000000000000
for i in range(n):
    for j in range(m):
        if a[i][j]=='*':
            minj = min(j,minj)
            maxi = i
            maxj = max(maxj,j)
            mini = min(mini,i)
print(max(maxi-mini+1,maxj-minj+1))

s = input().split()
n = int(s[0])
m = int(s[1])
a = []
b = []
c = []
d = []
for i in range(n):
    a.append(input())
for j in range(m):
    for i in range(n):
        if a[i][j] == '*':
            b.append(i)

c.append(max(b) - min(b)+1)
b = []
for i in range(n):
    for j in range(m):
        if a[i][j] == '*':
            b.append(j)
d.append(max(b) - min(b)+1)
print(max(max(c),max(d)))






















    


n, m = map(int, input().split())
mxx, mxy, mnx, mny = 0, 0, n + 1, m + 1
for i in range(0, n):
    line = input()
    for j in range(0, m):
        if line[j] == '*':
            mxx = max(mxx, i)
            mxy = max(mxy, j)
            mnx = min(mnx, i)
            mny = min(mny, j)
print(max(mxx - mnx + 1, mxy - mny + 1))

def main():
    import sys
    input = sys.stdin.readline
    n, m = [int(i) for i in input().split()]
    x1 = n - 1
    x2 = 0
    y1 = m - 1
    y2 = 0
    for i in range(n):
        s = input()
        for j in range(m):
            if s[j] == '*':
                x1 = min(x1, i)
                x2 = max(x2, i)
                y1 = min(y1, j)
                y2 = max(y2, j)
    print(max(x2 - x1, y2 - y1) + 1)

main()

n, m = [int(x) for x in input().split()]
minX = m+1; maxX = -1; minY = n+1; maxY = -1
for i in range(n):
	line = input()
	j = 0
	for c in line:		
		if c == '*':
			if minX > j: minX = j
			if maxX < j: maxX = j
			if minY > i: minY = i
			if maxY < i: maxY = i
		j += 1

print(max(maxX - minX + 1, maxY - minY + 1))


n,m=list(map(int,input().split()))
a=[]
l=m+1
r=-1
u=n+1
d=-1
lma=m+1
rma=-1
uma=n+1
dma=-1
for i in range(n):
    a.append(input().strip())
    if a[i].find('*')!=-1:
        l=a[i].find('*')
        r=a[i].rfind('*')
    if l<lma:
        lma=l
    if r>rma:
        rma=r
    if '*' in a[i] and uma==n+1:
        uma=i
    if '*' in a[i] and uma!=n+1:
        dma=i
print(max(dma-uma+1, rma-lma+1))


n, m = map(int,input().split())
minv = n
ming = m
maxv = 0
maxg = 0
i=0
while (i < n):
 str = input()
 j=0
 while (j < m):
  if (str[j] == '*'):
   if (minv > i): minv = i
   if (maxv < i): maxv = i
   if (ming > j): ming = j
   if (maxg < j): maxg = j
  j+= 1
 i += 1
if ((maxv - minv) > (maxg - ming)):
 n = maxv - minv + 1
 print(n)
else:
 m = maxg - ming + 1
 print(m)

z = input().split()
a = []
for i in range(2):
    a.append(int(z[i]))
n = a[0]
m = a[1]
b = []
x1 = 1001
x2 = 0
y1 = 1001
y2 = 0
for i in range(n):
    b.append(str(input()))
for i in range(n):
    for j in range(m):
        if b[i][j] == '*':
            if i < y1 :
                y1 = i
            if j < x1:
                x1 = j
            if i > y2:
                y2 = i
            if j > x2:
                x2 = j
x = x2 - x1 + 1
y = y2 - y1 + 1
if x > y:
    print(x)
else:
    print(y)
    


n,m=list(map(int,input().split()))
a=[list(input()) for i in range(n)]
ima=0
jma=0
imi=n+1
jmi=m+1
for i in range(n):
	for j in range(m):
		if a[i][j]=='*':
			if i<imi:
				imi=i
			if i>ima:
				ima=i
			if j<jmi:
				jmi=j
			if j>jma:
				jma=j
if ima-imi+1>0 and ima-imi+1>=jma-jmi+1:
	print(ima-imi+1)
elif jma-jmi+1>0 and jma-jmi+1>=ima-imi+1:
	print(jma-jmi+1)
elif jma-jmi<=0 and ima-imi<=0:
	print(0)


3

nm = (str(input()).split(" "))
prever = int(nm[0])
posver = 0
pregor = int(nm[1])
posgor = 0

z = 1
while z <= int(nm[0]):
		al = list(str(input()))
		rar = al.count("*")
		if rar != 0:
				if prever > z:
						prever = z
				if posver < z:
						posver = z
		x = 0
		while x <= (len(al) - 1):
				if al[x] == '*':
						if pregor > x:
								pregor = x
						if posgor < x:
								posgor = x
				x += 1
		z += 1

s1 = abs(pregor - posgor) + 1
s2 = abs(prever - posver) + 1

if s1 >= s2:
		s2 = s1
elif s2 > s1:
		s1 = s2
print(s1)


n,m = list(map(int,input().split()))
b = True
nach = 0
con = 0
nn = 0
cc = 0
for i in range(n):
    s = input()
    c = s.count('*')
    bb = True
    for j in range(m):
        if bb:
            if s[j] == '*':
                bb = False
                if b:
                    nn = j
                else:
                    nn = min(nn,j)
        if s[j] == '*':
            cc = max(cc,j)
    if b:
        if c != 0:
            b = False
            nach = i
            con = i
    if c != 0:
        con = i
m1 = cc - nn + 1
m2 = con - nach + 1
#print(m1,m2)
print(max(m1,m2))