Cave Escape

You are given a cave map represented by an R × C grid of characters. Each cell can be one of the following:

• . : An empty cell initially without any expedition member. Empty cells can accommodate arbitrarily many team members.
• P : A cell that initially contains exactly one expedition team member. All team members start in distinct cells, and none of them is located at an exit.
• * : An obstacle cell that cannot be traversed by any team member.
• O : An exit cell. The input guarantees that any exit cell is located on the boundary of the grid, i.e. only the first row, the last row, the first column, and the last column may contain O (or obstacles *).

Furthermore, the input guarantees that the entire cave is enclosed by either obstacles or exit cells; this means that every cell in the first row, the last row, the first column, and the last column is either * or O.

Your task is to determine how many expedition team members can escape the cave. A team member can escape if there is a path from its starting cell (marked with P) to any exit cell (marked with O). Moving is allowed in the four cardinal directions (up, down, left, right) and a team member can pass through any cell that is not an obstacle (*); note that empty cells (.) and cells with a team member (P) behave identically with respect to movement.

Hint: Consider performing a multi-source BFS starting from all exit cells.

inputFormat

The first line contains two integers R and C (R, C ≥ 1), representing the number of rows and columns of the grid.

Each of the following R lines contains a string of C characters representing a row of the cave map.

You can assume that for any cell on the boundary (i.e. in the first row, the last row, the first column, or the last column), the character is either * or O.

outputFormat

Output a single integer: the number of expedition team members (P) that can reach an exit cell (O).

sample

3 3
O.P
...
*O*

1