수중 여행

루시가 그루와 부하 둘을 납치해 반악당 연맹의 비밀 수중 본부로 데려가려 한다. 여정의 마지막 구간을 위해 자동차를 잠수정으로 개조했고, 가는 길에 수중 터널을 하나 지난다.

루시는 자동차의 소나로 터널의 깊이와 길이를 재고, 터널 바닥에서 솟아오른 석순 여러 개의 높이와 거리도 잰다. 터널 안에는 강한 물살이 흘러서 자동차를 1초에 1미터씩 앞으로 밀어낸다. 루시는 1초마다 자동차를 1미터 위로 올리거나, 같은 깊이를 유지하거나, 1미터 아래로 내릴 수 있다.

터널을 좌표로 나타내자. 거리는 왼쪽 끝에서 0으로 시작해 오른쪽으로 갈수록 커진다. 깊이는 천장 바로 아래 줄이 0이고 아래로 갈수록 커진다. 깊이가 $D$인 터널에서 자동차가 있을 수 있는 깊이는 $0$부터 $D-1$까지이고, 깊이 $-1$이 천장, 깊이 $D$가 바닥이다. 거리 $d$에 있는 높이 $h$짜리 석순은 바닥에서 $h$미터 솟아 있으므로, 거리 $d$의 깊이 $D-h$부터 $D-1$까지를 막는다.

자동차는 터널의 왼쪽 위 모서리, 즉 거리 0, 깊이 0에서 출발한다. 길이가 $n$인 터널에서는 $n-1$미터를 나아간 시점에 끝까지 무사히 도달한 것으로 본다. 그래서 행동 순서 하나는 $n-1$개의 행동으로 이루어진다.

행동을 하나 실행할 때마다 거리가 1 늘어나고, 깊이는 ^면 1 줄고 >면 그대로이며 v면 1 는다. 이동한 뒤의 위치를 다음 순서로 판정한다. 깊이가 0보다 작으면 천장에 부딪힌 것이고, 깊이가 $D$ 이상이면 바닥에 부딪힌 것이며, 그 칸이 석순에 막혀 있으면 석순에 부딪힌 것이다. 한 번이라도 부딪히면 자동차는 그 자리에서 멈추고 남은 행동은 실행하지 않는다.

행동 순서가 여러 개 주어진다. 각각에 대해 자동차가 천장, 바닥, 석순 중 무엇에 부딪히는지, 아니면 터널을 무사히 통과하는지 판정하라.

그림은 깊이 3, 길이 5인 터널을 보여 준다. 석순은 둘인데 하나는 높이 1미터에 거리 2, 다른 하나는 높이 2미터에 거리 3이다. 행동 순서 >v>>를 따르면 자동차는 오른쪽으로 1미터 가고, 다음으로 오른쪽 아래로 1미터 간 다음, 다시 오른쪽으로 가려다 두 번째 석순에 부딪힌다. 그 석순이 없었다면 같은 순서로 터널 끝까지 갔을 것이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

Tunnel depth D length L
	S stalagmites
	h1 meter stalagmite d1 meters distant
	...
	hS meter stalagmite dS meters distant
	Q sequences
	행동 순서 1
	...
	행동 순서 Q

숫자가 아닌 단어(Tunnel, depth, length, stalagmite, meters, distant, sequences 등)는 형식을 읽기 좋게 만드는 장식이고, 단수형과 복수형이 섞여 나온다. 줄 앞의 공백과 탭, 테스트 케이스 사이의 빈 줄도 무시한다. 의미가 있는 것은 숫자와 행동 순서 문자열이 나오는 차례뿐이다.

$D$는 터널의 깊이, $L$은 터널의 길이, $S$는 석순의 개수다. 이어서 석순마다 높이 $h$와 거리 $d$가 한 줄씩 주어진다. 그다음 행동 순서의 개수 $Q$가 오고, 행동 순서가 한 줄에 하나씩 주어진다. 각 행동 순서는 ^, >, v로만 이루어진 길이 $L-1$의 문자열이다. ^는 깊이를 1 줄이고, >는 깊이를 유지하며, v는 깊이를 1 늘린다.

제한:

• $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$
• 모든 테스트 케이스에 걸친 $Q \times (L-1)$의 합은 $10^6$ 이하

같은 거리에 석순이 여러 개 있을 수 있고, 그때 그 거리는 가장 높은 석순만큼 막힌다.

각 테스트 케이스마다 먼저 Case: k를 출력한다. $k$는 1부터 시작하는 테스트 케이스 번호다.

이어서 입력에 주어진 차례대로 행동 순서마다 한 줄씩 Sequence s r 형식으로 출력한다. s는 입력에 주어진 행동 순서 문자열 그대로이고, r은 다음 넷 중 하나다.

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