Orienteering

Interview

Time limit6sMemory limit1024 MB

Summary

Find the fewest arrows Springoalla must skip so that she ends at a given cell, starting at the top left moving right.

Level: Medium5 of 10
Topics: Graph, BFS, Simulation
Solved: No attempts yet

Problem

Springoalla has started orienteering, but to be honest she is not very good at it. Even though arrows are posted along the way, she gets lost almost every time. The forest she runs in can be seen as a rectangular grid with $N$ rows and $M$ columns, with arrows of four kinds: ^, >, v and <.

A dot (.) means the cell has no arrow. Springoalla enters the top left cell, running to the right. When she reaches an arrow, she turns automatically and runs in the direction the arrow points. Sometimes, though, she misses an arrow and keeps going straight past it.

Given a position in the forest, find the minimum number of arrows Springoalla must have missed to end up there. She never runs off the edge of the forest. Whether she misses an arrow does not depend on whether she has been at that cell before, so missing the same arrow twice counts as two misses. There is always at least one way she could have ended up at the given position.

Input

The first line contains four integers $N$ , $M$ , $R$ and $C$ ( $1 \leq R \leq N \leq 800$ , $1 \leq C \leq M \leq 800$ ): the height and width of the forest, and the row and column where Springoalla finishes. Rows are numbered 1 to $N$ and columns 1 to $M$ . The next $N$ lines each contain $M$ characters describing the forest. Each character is ., v (down), ^ (up), < (left) or > (right).

Output

Print a single integer: the minimum number of arrows Springoalla must have missed.

Hint

In the first case, she missed every downward arrow except one. In the second case, she missed the middle arrow twice. In the third case, she missed no arrows.

Examples3

Example 1

Input

3 10 2 1
..vvvvvvv>
..vvvvvv<^
<<<<<<<<..

Expected output

Example 2
Input
```
3 3 2 1
.v.
.^<
.>^
```
Expected output
```
2
```
Example 3
Input
```
2 2 2 1
vv
^<
```
Expected output
```
0
```