포뮬러 레이싱

신생 포뮬러 레이싱 팀 Irarref가 당신의 도움을 필요로 합니다. Irarref에는 정말 실력 있는 드라이버가 한 명도 없지만, 그래도 포뮬러 레이싱을 제패하고 싶어 합니다. 공정성 따위는 신경 쓰지 않는 이 팀은 드라이버의 조작이 거의 필요 없는 완전 자동 주행 제어 장치를 만들고 있습니다.

이 자동 주행 제어 장치를 실제 트랙에서 시험하다가 소중한 차를 망가뜨리는 위험을 감수하기 전에(드라이버는 별로 아끼지 않습니다), 그들은 먼저 컴퓨터 시뮬레이션으로 검증하고자 합니다.

당신은 주어진 트랙 위에서 자동차의 움직임을 시뮬레이션해야 합니다. 문제를 단순화하기 위해, 자동차는 2차원 격자의 칸 위에서 8방향(수평, 수직, 대각선)으로만 이동할 수 있습니다. 방향은 아래와 같이 부호화되며, 자동차는 가운데에 있습니다.

701
6 2
543

방향 0은 위쪽을 가리키고, 번호는 시계 방향으로 증가합니다.

매 턴마다 자동차는 다음 명령 중 정확히 하나를 실행합니다.

명령을 적용한 뒤, 자동차는 현재 방향으로 현재 속도만큼의 칸 수를 이동하며, 이전 위치와 새 위치 사이의 모든 칸을 지나갑니다. accelerate나 brake로 인한 속도 변화는 그 턴의 이동 전에 적용되고, left나 right로 인한 방향 변화도 이동 전에 적용됩니다.

트랙은 2차원 정규 격자입니다. 각 칸은 도로, 비도로 공간(그래도 주행 가능), 출발/결승선(도로이자 주행 가능), 벽 중 하나입니다.

모든 자동차는 속도 0으로 출발하며, 절대 넘을 수 없는 최대 속도를 가집니다. 자동차가 비도로 공간을 지나가면 다음 턴이 시작될 때(그 턴의 명령이 적용되기 전에) 속도가 1로 줄어들지만, 현재 턴의 이동은 현재 속도로 끝까지 완료됩니다. 자동차가 벽으로 이동해 들어가면 충돌하며, 그 자동차의 시뮬레이션은 즉시 멈추고 더 이상의 턴은 없습니다.

각 자동차는 트랙에 혼자 있으므로, 자동차 간 충돌은 고려하지 않아도 됩니다.

첫째 줄에는 시나리오의 수가 주어집니다.

각 시나리오는 트랙의 너비 $w$와 높이 $h$가 적힌 줄로 시작합니다($1 \le w, h \le 1000$). 이어지는 $h$개의 줄은 트랙의 배치를 나타내며, 도로, 비도로 공간, 출발/결승선, 벽은 각각 x, ., s, W로 표현됩니다. 트랙의 왼쪽 위 모서리는 $(0, 0)$, 오른쪽 아래 모서리는 $(w - 1, h - 1)$이며, 좌표는 $x$가 수평, $y$가 수직인 쌍 $(x, y)$로 주어집니다.

트랙 설명 다음에는 시뮬레이션할 자동차의 수 $n$이 적힌 줄이 옵니다. 각 자동차는 두 줄로 주어집니다.

• 자동차의 초기 $x$좌표, 초기 $y$좌표, 방향 $d$, 최대 속도 $m$이 하나의 공백으로 구분된 정수로 적힌 줄. 여기서 $0 \le x \le w - 1$, $0 \le y \le h - 1$, $0 \le d \le 7$, $1 \le m$입니다.
• 각 문자가 하나의 명령을 나타내는 명령 문자열이 적힌 줄. m, a, b, l, r은 각각 move-on, accelerate, brake, left, right를 뜻합니다. 한 자동차의 명령 수는 최소 1개, 최대 10000개입니다.

자동차의 초기 위치는 절대 벽이 아니며, 자동차는 충돌하지 않고 트랙 영역을 벗어나는 일이 없습니다.

각 시나리오에 대해 먼저 Scenario #i: 줄을 출력합니다. 여기서 i는 1부터 시작하는 시나리오 번호입니다. 턴은 0부터 번호가 매겨지므로, 각 자동차의 첫 번째 명령이 턴 0입니다.

그다음, 시나리오의 각 자동차에 대해 다음을 출력합니다.

• 결과 줄 하나. 자동차가 충돌하지 않았다면 최종 위치(x좌표와 y좌표), 방향, 속도를 하나의 공백으로 구분해 출력합니다. 충돌했다면 충돌 지점(x좌표와 y좌표), 충돌 순간의 방향과 속도를 출력한 뒤 crashed를 하나의 공백으로 구분해 붙입니다.
• 이어서, 자동차가 이동해 들어간 출발/결승선 칸마다(들어간 칸 하나당 한 줄, 들어간 순서대로) crossing startline: 뒤에 x좌표, y좌표, 방향, 속도, 그리고 그 칸에 들어간 턴 번호를 하나의 공백으로 구분해 출력합니다.

연속한 두 시나리오 사이에는 빈 줄을 하나 넣어 구분합니다.