Practice Flood fill and BFS with the exercise "The Other Side"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Flood fill
BFS
DFS
graph traversal

Statement

Goal

Placrates, the labyrinth engineer, is facing a simple puzzle. Given an h×w grid made of + and # characters, the objective to count the number of + characters in the leftmost column from which there exists a path to the rightmost column.

The path can be traced through a series of moves. Each move can be either horizontal or vertical, but not diagonal. Finally, valid moves pass through + characters only.

Input

Line 1 : The height h of the grid.
Line 2 : The width w of the grid.
Next h lines: The rows of the grid, where each row is composed of w space separated characters.

Output

Line 1 : The number of + characters in the leftmost column from which there exists a path to the rightmost column.

Constraints

2 ≤ h,w ≤ 12

Example

Input

2
3
+ + +
+ + +

Output

Solve it

A higher resolution is required to access the IDE