루카
면접 대비시간 제한1초메모리 제한512 MB
루카의 고정된 위치와 단위 걸음으로 이루어진 이동 경로가 주어질 때, 이동자가 루카의 칸이나 주변 여덟 칸에 도착한 걸음의 번호를 오름차순으로 출력한다.
문제
루카는 2003년에 DMIH에 열흘 일찍 도착해서, 크레스 섬을 매일 산책하며 과제에 대해 속삭이는 출제자들의 대화를 엿들어 유용한 정보를 얻으려 했다.
크레스 시를 평면 위의 좌표 격자로 생각하자. 출제자들은 좌표 (0, 0)에 있는 호텔에서 출발해, 매 걸음마다 좌표 격자를 따라 네 방향 중 하나로 단위 거리만큼 움직인다: 동쪽(x축 양의 방향), 북쪽(y축 양의 방향), 서쪽, 남쪽이다.
루카는 좌표 (x, y)에 있으며, 출제자들이 루카의 바로 옆, 즉 루카가 있는 위치나 그 여덟 개의 인접 위치(가로, 세로, 대각선 방향) 중 하나에 있을 때에만 그들이 하는 말을 들을 수 있다. 출제자들이 루카가 들을 수 있는 위치에 있게 되는 걸음의 번호를 구하시오.
입력
첫째 줄에 공백 하나로 구분된 두 정수 x와 y가 주어진다 (−10 000 ≤ x, y ≤ 10 000). 이는 루카가 있는 위치다.
둘째 줄에 정수 k가 주어진다 (1 ≤ k ≤ 100 000). 이는 걸음의 수다.
셋째 줄에 출제자들이 걸어간 길을 나타내는 길이 k의 문자열이 주어진다. 이 문자열의 각 문자는 대문자 “I”, “S”, “Z”, “J” 중 하나이며 각각 동쪽, 북쪽, 서쪽, 남쪽을 뜻한다.
출력
루카가 어느 순간에도 출제자들의 말을 들을 수 없었다면 “-1”을 출력한다.
그렇지 않다면 문제의 걸음 번호를 오름차순으로 한 줄에 하나씩 출력한다.