山脉的轮廓以“.”的矩形表格的形式示意性地指定。 (空白区域)和“*”(山的一部分)。每个表列至少包含一个星号。保证任何“*”字符要么位于矩阵的底行,要么在其正下方有另一个“*”字符。
........................*..*.......*.**.......*.**..*...**.************ 山脉的示例图像。
旅游路线从左到右穿过整个山脉。每天,游客都会向右移动 - 到图中相邻的列。当然,每次他上升(或下降)到山的最高点时,都会在相应的列中。
假设游客最初位于第一列的最高点,并将在最后一列的最高点结束他的路线,找到两个值:
- 每日最大上升(如果山脉轮廓没有上升,则等于 0),
- 当天的最大下降(如果山脉轮廓中没有下降,则等于 0)。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100) — 分别是原理图图像中的行数和列数。
接下来是 n 行,每行 m 个字符 - 山脉的示意图。示意图中的每个符号都是“.”。或者 ”*”。矩阵的每一列至少包含一个“*”字符。保证任何“*”字符要么位于矩阵的底行,要么在其正下方有另一个“*”字符。
输出
打印两个空格分隔的整数:
- 每日最大上升值(如果山脉轮廓没有上升,则为 0),
- 当天最大下降值(如果山脉剖面中没有下降,则为 0)。
示例
输入 #1
6 11 ........... .........*. .*.......*. **.......*. **..*...**. ***********
输出 #1
3 4
输入 #2
5 5 ....* ...** ..*** .**** *****
输出 #2
1 0
输入 #3
8 7 ....... .*..... .*..... .**.... .**.*.. .****.* .****** *******
输出 #3
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)之间。