Профиль горного хребта схематично задан в виде прямоугольной таблицы из символов «.» (пустое пространство) и «*» (часть горы). Каждый столбец таблицы содержит хотя бы одну «звёздочку». Гарантируется, что любой из символов «*» либо находится в нижней строке матрицы, либо непосредственно под ним находится другой символ «*».  ...........

.........*.

.*.......*.

**.......*.

**..*...**.

***********   Пример изображения горного хребта.  

Маршрут туриста проходит через весь горный хребет слева направо. Каждый день турист перемещается вправо — в соседний столбец в схематичном изображении. Конечно, каждый раз он поднимается (или опускается) в самую верхнюю точку горы, которая находится в соответствующем столбце.

Считая, что изначально турист находится в самой верхней точке в первом столбце, а закончит свой маршрут в самой верхней точке в последнем столбце, найдите две величины:  наибольший подъём за день (равен 0, если в профиле горного хребта нет ни одного подъёма),  наибольший спуск за день (равен 0, если в профиле горного хребта нет ни одного спуска). 


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

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

Далее следуют n строк по m символов в каждой — схематичное изображение горного хребта. Каждый символ схематичного изображения — это либо «.», либо «*». Каждый столбец матрицы содержит хотя бы один символ «*». Гарантируется, что любой из символов «*» либо находится в нижней строке матрицы, либо непосредственно под ним находится другой символ «*».


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

Выведите через пробел два целых числа:  величину наибольшего подъёма за день (или 0, если в профиле горного хребта нет ни одного подъёма),  величину наибольшего спуска за день (или 0, если в профиле горного хребта нет ни одного спуска). 


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

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

Входные данные
5 5
....*
...**
..***
.****
*****

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

Входные данные
8 7
.......
.*.....
.*.....
.**....
.**.*..
.****.*
.******
*******

Выходные данные
6 2



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

В первом тестовом примере высоты гор равны: 3, 4, 1, 1, 2, 1, 1, 1, 2, 5, 1. Наибольший подъем равен 3 и находится между горой номер 9 (её высота равна 2) и горой номер 10 (её высота равна 5). Наибольший спуск равен 4 и находится между горой номер 10 (её высота равна 5) и горой номер 11 (её высота равна 1).

Во втором тестовом примере высоты гор равны: 1, 2, 3, 4, 5. Наибольший подъём равен 1 и находится, например, между горой номер 2 (ее высота равна 2) и горой номер 3 (её высота равна 3). Так как в данном горном хребте нет спусков, то величина наибольшего спуска равна 0.

В третьем тестовом примере высоты гор равны: 1, 7, 5, 3, 4, 2, 3. Наибольший подъём равен 6 и находится между горой номер 1 (её высота равна 1) и горой номер 2 (её высота равна 7). Наибольший спуск равен 2 и находится между горой номер 2 (её высота равна 7) и горой номер 3 (её высота равна 5). Такой же спуск находится между горой номер 5 (её высота равна 4) и горой номер 6 (её высота равна 2).

Difficulty: MEDIUM

Starter code:

Solutions:
def main():
	(n, m) = [int(i) for i in input().split()]
	d = [list(input()) for i in range(n)]
	a = [0] * m
	for i in range(m):
		for j in range(n):
			if d[j][i] == '*':
				a[i] += 1
	x = y = 0
	for i in range(1, m):
		if a[i] > a[i - 1]:
			x = max(x, a[i] - a[i - 1])
		else:
			y = max(y, a[i - 1] - a[i])
	print(x, y)
main()


(n, m) = map(int, input().split())
a = [0] * m
for i in range(n):
	b = list(input().rstrip())
	for j in range(m):
		if b[j] == '*':
			a[j] = max(a[j], n - i)
ma = 0
mi = 0
for i in range(m - 1):
	ma = max(ma, a[i + 1] - a[i])
	mi = min(mi, a[i + 1] - a[i])
print(ma, -mi)


(n, k) = (int(z) for z in input().split())
h = [0] * k
for i in range(n):
	s = input()
	for j in range(k):
		if s[j] == '*':
			h[j] += 1
mi = 0
ma = 0
for i in range(1, k):
	if h[i - 1] - h[i] > mi:
		mi = h[i - 1] - h[i]
	if h[i] - h[i - 1] > ma:
		ma = h[i] - h[i - 1]
print(ma, mi)


(h, w) = list(map(int, input().split()))
high = [0 for i in range(w)]
for i in range(h, 0, -1):
	s = input()
	for j in range(w):
		if s[j] == '*':
			high[j] = max(i, high[j])
mx = 0
mn = 0
for i in range(w - 1):
	mx = max(mx, high[i + 1] - high[i])
	mn = min(mn, high[i + 1] - high[i])
print(abs(mx), abs(mn))


(n, m) = list(map(int, input().split()))
p = []
for i in range(n):
	p.append(list(input()))
e = []
for i in range(m):
	col = 0
	for t in range(n):
		if p[t][i] == '*':
			col += 1
	e.append(col)
max1 = 0
max2 = 0
for i in range(m - 1):
	max1 = max(max1, e[i + 1] - e[i])
for i in range(1, m):
	max2 = min(max2, e[i] - e[i - 1])
print(max1, -max2)


(h, w) = list(map(int, input().split()))
mountains = [input() for i in range(h)]
heights = [0 for i in range(w)]
for x in range(w):
	for y in range(h):
		if mountains[h - 1 - y][x] == '*':
			heights[x] = y
up = 0
down = 0
for i in range(w - 1):
	a = heights[i]
	b = heights[i + 1]
	c = abs(a - b)
	if a > b and c > down:
		down = c
	if a < b and c > up:
		up = c
print(up, down)


(n, m) = list(map(int, input().split()))
pole = []
for i in range(n):
	s = input()
	pole.append(s)
ans = []
for j in range(m):
	for i in range(n):
		if pole[i][j] == '*':
			ans.append(n - i)
			break
ans2 = 0
ans1 = 0
newans = []
newans.append(ans[0])
for i in ans:
	newans.append(i)
newans.append(ans[-1])
for i in range(1, m + 1):
	ans1 = max(ans1, newans[i] - newans[i - 1])
	ans2 = max(ans2, newans[i] - newans[i + 1])
print(ans1, ans2)


(n, m) = map(int, input().split())
A = [0] * n
for i in range(n):
	per = input()
	A[i] = per
t = n
for i in range(n):
	if A[i][0] == '*':
		t = i
		break
per1 = 0
per2 = 0
for j in range(1, m):
	s = m
	for i in range(n):
		if A[i][j] == '*':
			s = i
			break
	if t > s:
		per1 = max(per1, t - s)
	else:
		per2 = max(per2, s - t)
	t = s
print(per1, per2)


(n, m) = map(int, input().split())
maps = []
for i in range(n):
	maps.append(input())
(up, down) = (0, 0)
for i in range(m):
	current = 0
	for j in range(n):
		if maps[j][i] == '*':
			current += 1
	if i:
		up = max(up, current - previous)
		down = max(down, previous - current)
	previous = current
print(up, down)


def mapp(s):
	return 1 if s == '*' else 0
(n, m) = list(map(int, input().split()))
x = []
for i in range(n):
	x.append(list(map(mapp, input())))
s = [0] * m
for i in range(m):
	for j in range(n):
		s[i] += x[j][i]
h = 0
f = 0
for i in range(1, m):
	if s[i] - s[i - 1] > h:
		h = s[i] - s[i - 1]
	elif s[i] - s[i - 1] < f:
		f = s[i] - s[i - 1]
print(h, abs(f))


(n, m) = map(int, input().split(' '))
matrix = []
for i in range(n):
	matrix.append(input())
m_value = []
for i in range(m):
	for j in range(n):
		if matrix[j][i] == '*':
			m_value.append(n - j)
			break
max_up = 0
max_down = 0
for i in range(1, m):
	if m_value[i] - m_value[i - 1] > max_up:
		max_up = m_value[i] - m_value[i - 1]
	if m_value[i] - m_value[i - 1] < max_down:
		max_down = m_value[i] - m_value[i - 1]
print(max_up, -max_down)


(n, m) = [int(x) for x in input().split()]
a = [[0] * m for i in range(n)]
for i in range(n):
	a[i] = list(input())
i = 0
j = 0
ans1 = 0
ans2 = 0
cnt = 0
temp = [0] * m
for i in range(n):
	for j in range(m):
		if a[i][j] == '*':
			temp[j] += 1
for i in range(1, m):
	ans1 = max(ans1, temp[i] - temp[i - 1])
	ans2 = max(ans2, temp[i - 1] - temp[i])
print(ans1, ans2)


(n, m) = map(int, input().split())
A = [0] * m
for i in range(n):
	B = list(input())
	for j in range(m):
		if B[j] == '*':
			A[j] += 1
mp = 0
ms = 0
for i in range(m - 1):
	if A[i] < A[i + 1] and A[i + 1] - A[i] > mp:
		mp = A[i + 1] - A[i]
	elif A[i] > A[i + 1] and A[i] - A[i + 1] > ms:
		ms = A[i] - A[i + 1]
print(mp, ms)


(n, m) = map(int, input().split())
(u, d) = (0, 0)
ans1 = 0
ans2 = 0
data = [input() for i in range(n)]
for i in range(m):
	help = ''
	for j in range(n):
		help += data[j][i]
	u = d
	d = n - help.find('*')
	delt = d - u
	if i != 0:
		if delt < 0:
			ans2 = max(ans2, abs(delt))
		else:
			ans1 = max(ans1, abs(delt))
print(ans1, ans2)


(n, m) = map(int, input().split())
arr = [list(map(str, input())) for i in range(n)]
ans = [0] * m
for i in range(n):
	for j in range(m):
		if arr[i][j] == '*':
			ans[j] += 1
pos = ans[0]
up = 0
dn = 0
for i in range(1, m):
	npos = ans[i]
	if npos < pos:
		dn = max(dn, pos - npos)
	else:
		up = max(up, npos - pos)
	pos = npos
print(up, dn)


(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	s = input()
	s = s.replace('', ' ')
	s = s[1:-1]
	a += [list(s.split())]
mp = 0
ms = 0
mv = [0] * m
for i in range(m):
	for j in range(n):
		if a[j][i] == '*':
			mv[i] = n - j
			break
for i in range(m - 1):
	mp = max(mp, mv[i + 1] - mv[i])
	ms = max(ms, mv[i] - mv[i + 1])
print(mp, ms)


s = input().split()
n = int(s[0])
m = int(s[1])
a = []
b = []
down = []
up = []
for i in range(n):
	a.append(input())
for i in range(m):
	for j in range(n):
		if a[j][i] == '*':
			b.append(n - j)
			break
for i in range(len(b) - 1):
	if b[i] <= b[i + 1]:
		up.append(b[i + 1] - b[i])
	else:
		down.append(b[i] - b[i + 1])
if len(down) == 0:
	down.append(0)
if len(up) == 0:
	up.append(0)
print(max(up), max(down))


def getMapH(Map):
	mapHieght = []
	temp = int(0)
	for x in range(len(Map[0])):
		for y in range(len(Map)):
			if Map[y][x] == '.':
				temp += 1
				continue
			else:
				break
		mapHieght += [len(Map) - temp]
		temp = 0
	return mapHieght

def getMaxdelta(mapH):
	res = int(0)
	for i in range(len(mapH) - 1):
		if mapH[i + 1] - mapH[i] > 0:
			res = max(res, mapH[i + 1] - mapH[i])
	return res

def getMindelta(mapH):
	res = int(0)
	for i in range(len(mapH) - 1):
		if mapH[i] - mapH[i + 1] > 0:
			res = max(mapH[i] - mapH[i + 1], res)
	return res
inStr = input()
(n, m) = inStr.split()
mymap = []
mapHieght = []
for i in range(int(n)):
	inStr = input()
	mymap += [inStr]
print(getMaxdelta(getMapH(mymap)), getMindelta(getMapH(mymap)))


(n, m) = list(map(int, input().split()))
a = [list(input()) for i in range(n)]
p1 = 0
pp = 0
pm = 0
sm = 0
d = [True] * m
for i in range(m):
	for j in range(n):
		if i == 0 and a[j][i] == '*' and d[i]:
			pp = n - j
			d[i] = False
		elif d[i] and a[j][i] == '*':
			p1 = n - j
			if pp > p1 and pp - p1 > sm:
				sm = pp - p1
			if p1 - pp > pm:
				pm = p1 - pp
			pp = p1
			p1 = n - j
			d[i] = False
print(pm, sm)


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

def main():
	(n, m) = read_ints()
	field = [list(input()) for _ in range(n)]
	heights = [sum([1 if field[j][i] == '*' else 0 for j in range(n)]) for i in range(m)]
	INF = 1 ** 10
	max_up = 0
	max_down = 0
	for i in range(m - 1):
		delta = heights[i + 1] - heights[i]
		max_up = max(max_up, delta)
		max_down = max(max_down, -delta)
	print(max_up, max_down)

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
a = []
for i in range(n):
	s = input()
	v = []
	for i in s:
		if i == '.':
			v.append(0)
		else:
			v.append(1)
	a.append(v)
sp = 0
pod = 0
for i in range(m - 1):
	s1 = 0
	s2 = 0
	for j in range(n):
		s1 += a[j][i]
		s2 += a[j][i + 1]
		if s1 - s2 < 0 and abs(s1 - s2) > pod:
			pod = abs(s1 - s2)
		elif s1 - s2 > 0 and abs(s1 - s2) > sp:
			sp = abs(s1 - s2)
print(pod, sp)


strin1 = str(input())
n = int(strin1.split()[0])
m = int(strin1.split()[1])
arr = [0] * m
for i in range(n):
	currStr = str(input())
	for j in range(m):
		if (currStr[j] == '*') & (arr[j] == 0):
			arr[j] = n - i
maxUp = 0
maxDown = 0
for i in range(m - 1):
	if arr[i + 1] > arr[i]:
		maxUp = max(arr[i + 1] - arr[i], maxUp)
	if (i > 0) & (arr[i] < arr[i - 1]):
		maxDown = max(arr[i - 1] - arr[i], maxDown)
	if (i == m - 2) & (arr[i] > arr[i + 1]):
		maxDown = max(arr[i] - arr[i + 1], maxDown)
print(maxUp, maxDown)


(n, m) = map(int, input().split())
a = [0] * m
for i in range(n):
	s = input()
	for j in range(m):
		if s[j] == '*':
			if a[j] == 0:
				a[j] = n - i
spusk = 0
pod = 0
for i in range(m - 1):
	p = a[i + 1] - a[i]
	if p > 0:
		if p > pod:
			pod = p
	else:
		p *= -1
		if spusk < p:
			spusk = p
print(pod, spusk)


(n, m) = list(map(int, input().split()))
A = [list(input()) for i in range(n)]
p = 0
s = 0
b = 0
B = []
for i in range(m):
	for j in range(n):
		if A[j][i] == '*':
			b += 1
	B.append(b)
	b = 0
for i in range(m - 1):
	if B[i] > B[i + 1] and B[i] - B[i + 1] > s:
		s = B[i] - B[i + 1]
	elif B[i] < B[i + 1] and B[i + 1] - B[i] > p:
		p = B[i + 1] - B[i]
print(p, s)