로봇 청소기 2

시간 제한12초메모리 제한1024 MB

요약

상자와 시작 칸이 있는 격자 창고가 주어질 때, 청소기가 방문하는 서로 다른 칸 수를 최대로 만드는 길이 N의 명령 문자열을 출력한다.

문제

로봇 청소기 문제는 격자에서 로봇 청소기가 몇 개의 칸을 방문하는지 세는 것이었다. 이 문제에서는 격자와 명령열의 길이가 주어지고, 청소기가 최대한 많은 서로 다른 칸을 방문하도록 하는 명령열을 찾아야 한다.

채점은 출제진의 해답과 비교하여 얼마나 좋은지를 기준으로 점수를 준다. 따라서 $100$ 점을 받기는 어려울 수 있지만, 부분 점수를 얻는 것은 그렇게 어렵지 않을 수 있다.

입력은 $10$ 개의 테스트 케이스로 이루어진다.

첫째 줄에는 정수 $T$ ( $0 \leq T \leq 10$ )가 주어지며, 이는 테스트 케이스의 번호이다 ( $0$ 은 아래의 예제 케이스이다).
둘째 줄에는 세 정수 $R$ ( $3 \le R \le 2000$ ), $C$ ( $3 \le C \le 2000$ ), $N$ ( $1 \le N \le 2000$ )이 주어진다. $R$ 과 $C$ 는 격자 모양 창고의 행과 열의 수이고, $N$ 은 명령열의 길이이다.
다음 $R$ 개의 줄은 격자 모양 창고의 상태를 나타낸다. 이 중 $i$ 번째 줄은 $i$ 번째 행의 상태를 나타내는 $C$ 개의 문자를 포함한다. 각 문자는 칸이 비어 있으면 점 ".", 상자가 있으면 "#", 로봇의 시작 위치이면 "O"이다. "O"를 포함하는 칸은 정확히 하나임이 보장된다. 또한 격자 가장자리에 있는 모든 칸은 "#"임이 보장된다.

"^", ">", "v", "<" 문자로만 이루어진 길이 $N$ 의 문자열을 한 줄에 출력한다. 이 문자열은 청소기가 따르게 될 명령열이다.

예제 1

입력

0
8 10 14
##########
#.#......#
#....#...#
##......O#
#........#
#..#.....#
#....#...#
##########

예상 출력

<v>^<v>v<^^><>