Underwater Trip

Lucy has kidnapped Gru and two minions to take them to the secret underwater headquarters of the Anti-Villain League. For the last part of the trip she converted her car into a submarine, and the route passes through an underwater tunnel.

Lucy uses the car's sonar to measure the depth and length of the tunnel, and the height and distance of the stalagmites sticking up from the tunnel floor. A strong current runs through the tunnel and carries the car 1 meter forward each second. Each second Lucy can steer the car 1 meter up, keep it at the same depth, or steer it 1 meter down.

Describe the tunnel with coordinates. Distance starts at 0 at the left end and grows to the right. Depth is 0 in the row just under the ceiling and grows downward. In a tunnel of depth $D$ the car may sit at depths $0$ through $D-1$, depth $-1$ is the ceiling, and depth $D$ is the floor. A stalagmite of height $h$ at distance $d$ rises $h$ meters from the floor, so at distance $d$ it blocks depths $D-h$ through $D-1$.

The car starts at the top left corner of the tunnel, at distance 0 and depth 0. In a tunnel of length $n$ the car has safely reached the end once it has travelled $n-1$ meters, so one action sequence consists of $n-1$ actions.

Each action advances the distance by 1 and changes the depth by $-1$ for ^, by $0$ for >, and by $+1$ for v. Check the position after the move in this order: a depth below 0 is a crash into the ceiling, a depth of $D$ or more is a crash into the floor, and a cell blocked by a stalagmite is a crash into that stalagmite. On the first crash the car stops where it is and the remaining actions are not carried out.

Several action sequences are given. For each one, decide whether the car hits the ceiling, the floor, or a stalagmite, or passes safely through the tunnel.

The picture shows a tunnel of depth 3 and length 5. There are two stalagmites: one is 1 meter high at distance 2, the other is 2 meters high at distance 3. With the sequence >v>> the car moves 1 meter right, then 1 meter down and to the right, and then hits the second stalagmite as it tries to move right again. Without that stalagmite the same sequence would reach the end of the tunnel.

The first line has the number of test cases $T$. Each test case has this shape:

Tunnel depth D length L
	S stalagmites
	h1 meter stalagmite d1 meters distant
	...
	hS meter stalagmite dS meters distant
	Q sequences
	sequence 1
	...
	sequence Q

Words that are not numbers (Tunnel, depth, length, stalagmite, meters, distant, sequences and so on) are decoration, and singular and plural forms are mixed. Leading spaces and tabs, and blank lines between test cases, are ignored too. Only the order of the numbers and of the action sequence strings matters.

$D$ is the depth of the tunnel, $L$ is its length, and $S$ is the number of stalagmites. One line per stalagmite then gives its height $h$ and its distance $d$. After that comes the number of action sequences $Q$, followed by one sequence per line. Each sequence is a string of exactly $L-1$ characters drawn from ^, >, and v, where ^ decreases the depth by 1, > keeps it, and v increases it by 1.

Limits:

• $1 \le T \le 50$
• $1 \le D \le 1000$
• $2 \le L \le 1000$
• $0 \le S \le 1000$
• $1 \le h \le D$
• $1 \le d \le L-1$
• $1 \le Q \le 1000$
• the sum of $Q \times (L-1)$ over all test cases is at most $10^6$

Several stalagmites may share one distance, and that distance is then blocked up to the tallest of them.

For each test case print Case: k first, where $k$ is the 1-based number of the test case.

Then print one line per action sequence, in input order, in the form Sequence s r. Here s is the action sequence exactly as it was given, and r is one of:

• Reached end of tunnel
• Crashed into stalagmite
• Crashed into tunnel floor
• Crashed into tunnel ceiling