A. Наибольший подъем
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Считая, что изначально турист находится в самой верхней точке в первом столбце, а закончит свой маршрут в самой верхней точке в последнем столбце, найдите две величины:

  • наибольший подъём за день (равен 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).