Practice Strings and Lists with the exercise "Criminal"

Learning Opportunities

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

Statement

Goal

You are a criminal. You are in search and capture, nobody should see you.

You are in an area of height H and width W.
You have to print how many people are watching you.

INFORMATION:
* .: nothing
* Y: you
* ^: person who looks up
* >: person who looks to the right
* v: person who looks down
* <: person who looks to the left
* other character: obstacle

RULES:
1. You:
* If you are in the field of vision of a person, that person is considered to be watching you.

2. The field of vision of the people:
* The field of vision increases by two characters (starting with 3) depending on where the person is looking:

........v........
.......###.......
......#####......
.....#######.....
....#########....
...###########...
..######Y######..
.###############.
#################
(is watching you)

* If an obstacle (!!OR ANOTHER PERSON!!) interferes with the field of vision of a person, the person cannot see what is behind the obstacle.

3. Obstacles:
* If the obstacle is right in front of the person, everything that is behind cannot be seen. If the obstacle is to the right or left of the person, the hidden area will increase by one (starting from 2):

........v........
.......###.......
......#####......
.....###x###.....
....####.#x##....
...#####.#..##...
..###x##Y#...##..
.###..##.#....##.
###...##.#.....##
(is not watching you)

(The physics of this puzzle is not realistic.)

Input

Line 1: An integer H for the height of the area.
Line 2: An integer W for the width of the area.
Next H lines: A string of W characters for one row of the area.

Output

Line 1: An integer for how many people are watching you.

Constraints

1 ≤ H, W ≤ 64
The area contains exactly one Y.

Example

Input

4
6
...v..
......
..Y.#<
...^..

Output

Solve it

A higher resolution is required to access the IDE