오리엔티어링

Springoalla는 오리엔티어링을 시작했지만, 솔직히 말해 그다지 잘하지 못한다. 실제로는 길을 안내하는 화살표가 설치되어 있는데도 거의 매번 길을 잃는다. 그녀가 달리는 숲은 $N$개의 행과 $M$개의 열로 이루어진 직사각형 격자로 볼 수 있으며, 서로 다른 네 종류의 화살표 ^, >, v, <가 배치되어 있다.

마침표 문자(.)는 칸에 화살표가 없음을 나타내는 데 사용된다. Springoalla는 오른쪽을 향해 달리면서 왼쪽 위 칸으로 들어온다. 화살표가 있는 곳에 도착하면 자동으로 방향을 바꾸어 화살표가 가리키는 방향으로 달리기 시작한다. 하지만 때로는 화살표를 놓치고 방향을 바꾸지 않은 채 그대로 직진하기도 한다.

숲의 한 위치가 주어질 때, Springoalla가 그곳에 도착하려면 최소 몇 개의 화살표를 놓쳤어야 하는가? 그녀는 숲 밖으로 달려 나간 적이 있을 수 없으며, 화살표를 놓치는지 여부는 이전에 그 위치를 방문했는지와 무관하다는 점에 유의하라 (예를 들어 같은 화살표를 두 번 놓쳤다면 두 번 놓친 것으로 센다). 주어진 위치에 도착할 수 있는 방법은 항상 적어도 하나 존재한다.

채점

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$50$| $N \leq 200$, $M \leq 200$

$2$ |$50$| 추가 제한 없음

첫째 줄에 네 수 $N$, $M$, $R$, $C$가 주어진다 ($1 \leq R \leq N \leq 800$, $1 \leq C \leq M \leq 800$). 이들은 각각 숲의 높이와 너비, 그리고 Springoalla가 마지막에 도착한 위치(행과 열)를 나타낸다 (행에는 $1$부터 $N$까지, 열에는 $1$부터 $M$까지 번호가 매겨진다). 이어서 숲을 설명하는, 각각 $M$개의 문자로 이루어진 $N$개의 줄이 주어진다. 각 문자는 ., v (아래), ^ (위), < (왼쪽), > (오른쪽) 중 하나이다.

수 하나를 출력한다. 이 수는 Springoalla가 놓쳤어야 하는 화살표 수의 최솟값이다.

예제 1의 설명: 아래쪽 화살표 중 하나를 제외하고 모두 놓쳤다.

예제 2의 설명: 가운데 화살표를 두 번 놓쳤다.

예제 3의 설명: 화살표를 하나도 놓치지 않는다.