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

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


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

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

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

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


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

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


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

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

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

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

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

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



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

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

 [Image] 

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

 [Image] 

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

 [Image]

Difficulty: MEDIUM

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
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
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(max(m1, m2))