Can you stay on the grid?
When designing a computer game, you are working on an
h-by-w grid. At each cell, there is a direction (<>v^) that points where you should move if you have appeared on that cell.You start at some random cell and move in the direction that the cell indicates. In some cases, you might get off the grid, which means the game is over.
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
As you are the designer of the game, you’d like to make sure those kinds of cells are not too many. So, you’d like to calculate the number of cells that starting from those, you’d always stay on the grid.
Input
The first line of the input contains two integers
h and w (1 ≤ h, w ≤ 1000).The next
h lines contain w characters that represent the direction one has to move if appeared on that cell (<>v^).Output
The program should print the number of cells starting from which, you’d always stay on the grid.
Examples
Input | Output |
4 5
>>v>>
^<<v<
v^^<>
<v^>< | 14 |
Explanation
> | > | v | > | > |
^ | < | < | v | < |
v | ^ | ^ | < | > |
< | v | ^ | > | < |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB