거대한 레버 도전

This is a problem with public tests.

퍼즐 게임을 좋아하시나요? 분명 좋아하실 겁니다! 이 문제는 여러분을 위해 준비한 특별한 도전입니다.

로봇이 복잡한 미로 안에 있습니다. 여러분의 임무는 로봇을 출발 위치에서 도착 지점까지 옮기는 것입니다. 로봇은 레버로 조작하며, 각 레버의 성질에 따라 미로 안에서 움직임이 정해집니다.

각 레버는 세 가지 속성을 가집니다.

1. 길이: 레버를 작동했을 때 로봇이 이동하는 거리입니다.
2. 차원: 이동 축입니다. $x$ 축(가로) 또는 $y$ 축(세로)입니다.
3. 상태: 이동 방향입니다. 양수(+) 또는 음수(-)입니다.

레버를 당기면 상태가 반대로 바뀝니다. 그다음 로봇은 바뀐 상태가 가리키는 방향으로 움직입니다. 새 상태가 양수이면 해당 축의 양의 방향으로 레버 길이만큼 이동합니다. 새 상태가 음수이면 음의 방향으로 이동합니다. 주의할 점이 있습니다. 로봇이 벽이나 미로의 경계에 부딪히면 멈추고, 다음 레버를 작동해야 다시 움직입니다.

로봇을 출발점에서 도착점까지 옮기십시오.

레벨은 10개뿐입니다. 모두 통과하십시오!

첫 줄에는 현재 테스트의 번호가 정수 하나로 주어집니다. 다음 줄에는 미로의 행 수 $n$과 열 수 $m$이 정수 두 개로 주어집니다($1 \leq n, m \leq 1000$). 그다음 줄에는 사용할 수 있는 레버의 개수 $k$가 주어집니다($1 \leq k \leq 100$).

각 레버는 <len><dim><state> 형식의 한 줄로 주어집니다. <len>은 1 이상 1000 이하의 정수이고, <dim>은 x 또는 y, <state>는 - 또는 +입니다.

이어지는 $n$개의 줄은 길이 $m$의 문자열로 미로를 나타냅니다.

• #은 벽입니다.
• .은 빈 칸입니다.
• @은 시작 위치입니다.
• $은 도착 위치입니다.

미로마다 시작 위치와 도착 위치가 각각 하나뿐입니다. 모든 테스트는 풀 수 있음이 보장됩니다.

$Ox$ 축은 왼쪽에서 오른쪽으로, $Oy$ 축은 위에서 아래로 향합니다.

로봇을 출발 위치에서 도착 지점까지 옮기기 위해 레버를 당기는 순서대로 레버 번호를 출력합니다. 레버 번호는 입력 순서대로 1부터 매겨집니다.

출력하는 레버 번호의 개수는 $10^5$을 넘으면 안 됩니다. 모든 테스트는 이 제한 안에서 풀 수 있음이 보장됩니다.