Shark Tour

The minions who rode in Lucy's car on an underwater trip were impressed by the many sharks they saw in the tunnel. When they got home they told the other minions, and now everyone wants to go back and see the sharks.

The sonar on Lucy's car reports the depth and the length of the tunnel together with the height and the distance of every stalagmite that rises from the tunnel floor. For the shark tour Lucy modified the sonar so that it also reports how many sharks can be seen from each location in the tunnel. Because of the viewing conditions, a shark is visible from exactly one location.

A current runs through the tunnel and carries the car 1 meter forward each second. Every second Lucy can steer the car up 1 meter, keep it at the same depth, or steer it down 1 meter.

Treat the tunnel as a grid. A tunnel of depth $D$ and length $N$ contains one location $(d, p)$ for every distance $d$ with $0 \le d \le N-1$ and every depth $p$ with $0 \le p \le D-1$. Depth $0$ is the ceiling and depth $D-1$ is the floor. A stalagmite of height $h$ standing at distance $d$ fills the $h$ lowest locations of that column, which are the depths $D-h$ through $D-1$. The car can never enter a filled location and can never leave the tunnel.

The car starts at the top left corner, distance $0$ and depth $0$, and it has safely reached the end of the tunnel once it has traveled $N-1$ meters. A path is therefore a sequence of $N-1$ actions, each written as one character. ^ steers the car up and decreases the depth by 1, > keeps it at the same depth, and v steers it down and increases the depth by 1. The car sees the sharks of every location it occupies, including the starting location and the last one. At least one path through the tunnel always exists.

The tunnel in the figure has depth 3 and length 5. One stalagmite is 1 meter high at distance 2, the other is 2 meters high at distance 3. The sonar reports 4 sharks at distance 2 depth 1, 3 sharks at distance 2 depth 0, 2 sharks at distance 4 depth 1, and 6 sharks at distance 1 depth 2. One second after the start the car is at depth 0 or depth 1, so it can never reach distance 1 depth 2. The action sequence >v^v passes through distance 2 depth 1 and distance 4 depth 1 and sees 6 sharks, and no path sees more.

Find the largest number of sharks a legal path sees, and the actions of such a path. The tunnel can be long and the sonar can report several thousand sightings, so checking every path one by one is too slow.

The first line contains the number of test cases $T$. Each test case is written in the form below. The spacing between the words and the indentation of the lines varies, so reading the integers in order is enough.

Tunnel depth D length N
	S stalagmites
	h meter stalagmite d meters distant
	K sightings
	c sharks d meters distant p meters down

The stalagmite line is repeated $S$ times and the sighting line is repeated $K$ times.

$1 \le T \le 20$, $1 \le D \le 100$, $2 \le N \le 10000$, $0 \le S \le N$, $1 \le h \le D-1$, $0 \le K \le 5000$, $1 \le c \le 1000$, and every distance satisfies $0 \le d \le N-1$ while every sighting depth satisfies $0 \le p \le D-1$. The sum of $D \times N$ over all test cases is at most $200000$. Every test case admits at least one path from the start to distance $N-1$. Two sighting lines can name the same location, and then their shark counts add up.

For each test case print two lines. The first line is Case: t, where $t$ is the number of the test case counted from 1. The second line is

Saw n sharks for sequence s

where $n$ is the largest number of sharks a legal path sees and $s$ is the $N-1$ actions of such a path.

Several paths can see $n$ sharks. Compare two action sequences character by character and look at the first position where they differ: the sequence whose character comes earlier in the order >, ^, v comes first. Print the sequence that comes first under this rule.