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