乔在互联网上受到了伤害。现在他正在房子里肆虐,摧毁了他所经过的一切。
Joe 的房子有 n 层,每层都是 m 个单元格的一部分。每个单元要么什么也不包含(它是一个空单元),要么有砖墙或混凝土墙(总是三者之一)。据信,每层楼的左右两侧都被混凝土墙包围。
现在乔在第 n 层,第一个牢房,从左到右数。在每一时刻,乔都有他的目光方向,向右或向左(总是两个方向之一)。最初,乔向右看。
乔通过特定的算法移动。他每秒都会进行以下操作之一:
- 如果乔正下方的单元格是空的,那么乔就会摔倒。也就是说,他移动到这个牢房时,注视方向被保留。
- 否则考虑当前注视方向的下一个单元格。 如果单元格是空的,那么乔就会移入其中,凝视方向将被保留。 如果这个牢房里有砖块,那么乔就会用额头打碎它们(牢房变空),并将视线方向转向相反的方向。 如果这个牢房有混凝土墙,那么乔只需将视线方向转向相反的方向(混凝土可以承受任意数量的额头撞击)。
乔一到达一楼的任何牢房就会平静下来。
下图显示了 Joe 在房子周围的活动示例。
确定乔需要多少秒才能平静下来。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 100, 1 ≤ m ≤ 104)。
接下来的 n 行包含对 Joe 房子的描述。这些行中的第 i 行包含对房屋第 (n - i + 1) 层的描述——一行由 m 个字符组成:“.”表示空单元格,“+”表示砖块,“#”表示混凝土墙。
保证第n层第一个单元格是空的。
输出
打印一个数字——乔到达一楼所需的秒数;否则,如果它永远不会发生,则打印单词“Never”(不带引号)。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
3 5 ..+.# #+..+ +.#+.
输出 #1
14
输入 #2
4 10 ...+.##+.+ +#++..+++# ++.#++++.. .+##.++#.+
输出 #2
42
输入 #3
2 2 .. ++
输出 #3
Never