Robot Vacuum 2

Time limit12sMemory limit1024 MB

Summary

Given a grid warehouse with boxes and a start cell, output a command string of length N that maximizes the number of distinct cells the vacuum visits.

Level: Hard9 of 10
Topics: Greedy, Simulation, Graph, Brute force
Solved: No attempts yet

Problem

The problem Robot Vacuum was about counting how many cells a robot vacuum visits in a grid. In this problem, you are given the grid and the length of the command sequence, and must instead find a command sequence that makes the vacuum visit as many different cells as possible.

Your score depends on how well your solution performs compared to the judges' solution. This means that getting $100$ points may be difficult, but collecting partial points does not have to be very hard.

Input

The input consists of $10$ test cases.

The first line contains an integer $T$ ( $0 \leq T \leq 10$ ), the number of the test case ( $0$ is the example case below).
The second line contains three integers: $R$ ( $3 \le R \le 2000$ ) and $C$ ( $3 \le C \le 2000$ ), the number of rows and columns in the grid-shaped warehouse, and $N$ ( $1 \le N \le 2000$ ), the length of the command sequence.
The following $R$ lines describe the grid-shaped warehouse. The $i$ -th of these lines contains $C$ characters describing the $i$ -th row. Each character is either a period "." if a cell is empty, a hash "#" if a cell contains a box, or "O" if the cell is the robot's starting position. Exactly one cell is guaranteed to contain "O". In addition, every cell on the edge of the grid is guaranteed to be "#".

Output

Print one line containing a string of length $N$ made up of the characters "^", ">", "v", "<". This is the command sequence the vacuum will follow.

Examples1

Example 1

Input

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

Expected output

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