상어 투어

루시의 잠수차를 타고 바닷속을 여행한 미니언들은 굴에서 본 수많은 상어에 깊은 인상을 받았다. 집에 돌아와 다른 미니언들에게 이야기하자, 이제 모두가 다시 가서 상어를 보고 싶어 한다.

루시의 잠수차에 달린 음파 탐지기는 굴의 깊이와 길이, 그리고 굴 바닥에서 솟아오른 석순 하나하나의 높이와 거리를 알려 준다. 상어 투어를 위해 루시는 탐지기를 고쳐서 굴의 각 지점에서 상어가 몇 마리나 보이는지도 알려 주도록 했다. 관측 조건 때문에 상어 한 마리는 정확히 한 지점에서만 보인다.

굴에는 물살이 흘러서 잠수차를 1초에 1미터씩 앞으로 밀어낸다. 루시는 1초마다 차를 1미터 위로 몰거나, 같은 깊이를 유지하거나, 1미터 아래로 몰 수 있다.

굴을 격자로 생각하자. 깊이가 $D$이고 길이가 $N$인 굴에는 $0 \le d \le N-1$인 거리 $d$와 $0 \le p \le D-1$인 깊이 $p$마다 지점 $(d, p)$가 하나씩 있다. 깊이 $0$이 천장이고 깊이 $D-1$이 바닥이다. 거리 $d$에 높이 $h$인 석순이 서 있으면 그 열의 아래쪽 $h$칸, 즉 깊이 $D-h$부터 $D-1$까지가 막힌다. 잠수차는 막힌 칸에 들어갈 수 없고, 굴 밖으로 나갈 수도 없다.

잠수차는 왼쪽 위 모서리인 거리 $0$, 깊이 $0$에서 출발하고, $N-1$미터를 나아가면 굴 끝에 무사히 도착한 것으로 본다. 따라서 경로는 행동 $N-1$개로 이루어지고, 각 행동은 문자 하나로 적는다. ^는 차를 위로 몰아 깊이를 1 줄이고, >는 같은 깊이를 유지하고, v는 아래로 몰아 깊이를 1 늘린다. 잠수차는 지나간 모든 지점의 상어를 본다. 출발 지점과 마지막 지점도 포함한다. 굴을 통과하는 경로는 항상 하나 이상 있다.

그림의 굴은 깊이가 3이고 길이가 5이다. 석순 하나는 거리 2에 높이 1로 서 있고, 다른 하나는 거리 3에 높이 2로 서 있다. 탐지기는 거리 2 깊이 1에 상어 4마리, 거리 2 깊이 0에 3마리, 거리 4 깊이 1에 2마리, 거리 1 깊이 2에 6마리가 보인다고 알려 준다. 출발한 지 1초 뒤에 잠수차는 깊이 0이나 깊이 1에 있으므로 거리 1 깊이 2에는 결코 닿지 못한다. 행동 순서 >v^v는 거리 2 깊이 1과 거리 4 깊이 1을 지나 상어 6마리를 보고, 이보다 많이 보는 경로는 없다.

경로 하나가 볼 수 있는 상어의 최대 마리 수와, 그만큼 보는 경로의 행동 순서를 구하라. 굴은 길 수 있고 탐지기가 알려 주는 관측 지점도 수천 개에 이를 수 있으므로, 모든 경로를 하나씩 확인하는 방법으로는 시간 안에 풀 수 없다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 아래 형식으로 주어진다. 단어 사이의 공백과 줄 앞의 들여쓰기는 일정하지 않으므로, 정수만 순서대로 읽으면 된다.

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

석순 줄은 $S$번, 관측 줄은 $K$번 반복된다.

$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$이고, 모든 거리는 $0 \le d \le N-1$, 모든 관측 깊이는 $0 \le p \le D-1$을 만족한다. 모든 테스트 케이스의 $D \times N$을 더한 값은 $200000$ 이하이다. 각 테스트 케이스에는 출발 지점에서 거리 $N-1$까지 가는 경로가 항상 하나 이상 있다. 관측 줄 두 개가 같은 지점을 가리킬 수 있고, 그때는 두 줄의 상어 수를 더한다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 줄은 Case: t이고, $t$는 1부터 세는 테스트 케이스 번호이다. 둘째 줄은 다음 형식으로 출력한다.

Saw n sharks for sequence s

$n$은 경로 하나가 볼 수 있는 상어의 최대 마리 수이고, $s$는 그만큼 보는 경로의 행동 $N-1$개이다.

상어를 $n$마리 보는 경로가 여러 개일 수 있다. 두 행동 순서를 앞에서부터 한 문자씩 비교해 처음으로 달라지는 자리를 보고, 그 자리의 문자가 >, ^, v 순서에서 더 앞선 쪽을 앞선 순서로 정한다. 이 기준으로 가장 앞서는 행동 순서를 출력한다.