오늘부터 우리는 (Me gustas tu)
면접 대비시간 제한1초메모리 제한1024 MB
N×M 격자와 목표 칸 (a,b)가 주어졌을 때, 어느 칸에서 출발하든 바람을 따라 (a,b)에 도달하도록 각 칸의 바람 방향을 정합니다.
문제
널 향한 설레임을 오늘부터 우리는
꿈꾸며 기도하는 오늘부터 우리는
저 바람에 노을 빛 내 맘을 실어 보낼게
그리운 마음이 모여서 내리는
바람이 부는 들판에서, 나의 마음을 너에게 실어 보내려고 한다.
들판은 크기의 격자로 나타낼 수 있다. 각 칸은 (, )와 같은 좌표로 나타낸다. 이 좌표는 위에서 번째, 왼쪽에서 번째에 있는 칸을 뜻한다. 들판의 각 칸에는 동, 서, 남, 북 중 한 방향으로 바람이 분다. 들판에는 네가 칸에 서 있고, 나의 마음이 격자 어딘가에 정확히 1개 있다.
나의 마음이 칸 에 있으면 다음과 같이 이동한다.
- 칸 에 동쪽 바람이 불면 로 이동한다.
- 칸 에 서쪽 바람이 불면 로 이동한다.
- 칸 에 남쪽 바람이 불면 로 이동한다.
- 칸 에 북쪽 바람이 불면 로 이동한다.
나의 마음이 네가 있는 칸에 닿으면 마음이 전해지고, 격자의 경계를 벗어나면 사라진다. 둘 중 어느 쪽도 아니면 마음은 계속 이동한다.
나의 마음이 네가 있는 칸에서 시작할 수도 있다. 이 경우 마음이 바로 전해진다.
나의 마음이 어디에서 출발하든 항상 너에게 전해질 수 있다고 한다. 이러한 바람의 배치를 구해 보자.
입력
첫째 줄에 과 이 주어진다.
둘째 줄에 와 가 주어진다. (, )
출력
개 줄에 걸쳐 바람의 배치를 나타내는 개의 문자를 출력한다.
칸 에 바람이 동쪽으로 불면 번째 줄의 번째 글자로 E를 출력한다. 서쪽, 남쪽, 북쪽으로 불면 같은 방식으로 W, S, N을 출력한다.
가능한 바람의 배치가 여러 개이면 아무거나 출력해도 된다.
모든 입력에 대해 가능한 바람의 배치가 있음을 증명할 수 있다.