루카
면접 대비시간 제한1초메모리 제한128 MB
격자 위를 이동하는 사람의 경로를 시뮬레이션하며 고정된 지점과 체비셰프 거리 1 이내에 있는 모든 시각을 출력합니다.
문제
루카는 대회 문제에 대한 힌트를 얻기 위해 전국 대회보다 열흘 일찍 도착했다. 그는 문제를 만드는 사람들이 매일 크레스 마을을 산책하며 문제에 대해 조용히 이야기한다는 사실을 알고 있다.
크레스 마을은 평면 좌표 격자로 표현할 수 있다. 문제를 만드는 사람들은 (0, 0)에서 산책을 시작하고, 매 차례마다 네 방향 중 하나로 한 칸 움직인다. 오른쪽으로 움직이면 x좌표가 1 증가하고, 위쪽으로 움직이면 y좌표가 1 증가하며, 왼쪽이나 아래쪽으로도 움직일 수 있다.
루카는 평면 좌표의 (X, Y)에 서 있다. 그는 문제를 만드는 사람들이 루카와 같은 위치에 있거나, 루카의 위치와 인접한 여덟 칸 중 하나에 있을 때만 대화의 일부를 들을 수 있다.
루카가 대화를 들을 수 있었던 모든 시각을 구하는 프로그램을 작성하라. 산책을 시작하기 전의 위치는 시각 0이고, i번째 이동을 마친 직후의 시각은 i이다.
입력
첫째 줄에 루카의 위치를 나타내는 두 정수 X와 Y가 주어진다. -10000 ≤ X, Y ≤ 10000이다.
둘째 줄에 정수 K가 주어진다. 1 ≤ K ≤ 100000이다.
셋째 줄에 문제를 만드는 사람들이 그날 이동한 경로를 나타내는 길이 K의 문자열이 주어진다. 각 문자는 다음 중 하나이다.
I: 동쪽, 즉 오른쪽으로 한 칸 이동S: 북쪽, 즉 위쪽으로 한 칸 이동Z: 서쪽, 즉 왼쪽으로 한 칸 이동J: 남쪽, 즉 아래쪽으로 한 칸 이동
출력
루카가 대화를 들을 수 있었던 시각을 엄격히 오름차순으로 출력한다. 각 시각은 한 줄에 하나씩 출력한다.
루카가 한 번도 대화를 들을 수 없었다면 첫째 줄에 -1을 출력한다.