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

.........*.

.*.......*.

**.......*.

**..*...**.

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

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

Считая, что изначально турист находится в самой верхней точке в первом столбце, а закончит свой маршрут в самой верхней точке в последнем столбце, найдите две величины:  наибольший подъём за день (равен 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: interview

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()
#n строк по m символов в каждой
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)