Klasy

바이트란트(Byteotia)의 아이들은 사방치기(폴란드어로 klasy)의 흥미로운 변형 놀이를 즐긴다. 보도블록 위에 한 변의 길이가 $n$인 정사각형이 그려져 있고, 이 정사각형은 $n^2$개의 똑같은 칸으로 나뉘어 있다. 아이들 중 한 명(이하 '참가자')이 할 일은 모든 칸에 정해진 규칙대로 번호를 매기는 것이다. 놀이를 시작하기 전에 참가자에게는 방위(북, 남, 서, 동 중 하나)와 허용된 회전 방향(오른쪽 또는 왼쪽)이 주어진다.

참가자는 정사각형의 네 모서리 칸 중 하나를 골라 그 칸 위에 서서, 주어진 방위를 향한 뒤, 시작 칸에 숫자 $1$을 적으며 번호 매기기를 시작한다. 매 이동마다 참가자는 다음과 같이 행동한다.

• 앞으로 한 칸 나아간다. 단, 이동한 뒤에도 정사각형 안에 남아 있고, 옮겨 갈 칸이 아직 번호가 매겨지지 않은 빈 칸일 때에만 그렇게 한다.
• 그렇지 않으면 허용된 방향으로 딱 한 번 방향을 튼 뒤, 앞으로 한 칸 나아간다.

참가자는 새로 방문하는 칸마다 다음 자연수를 차례로 적는다. 또한 첫 이동에서는 방향을 틀 수 없고, 오직 주어진 방위 그대로 앞으로 나아가야 한다. 따라서 시작 칸은 신중하게 골라야 한다. 예를 들어 정사각형의 한 변이 $5$이고, 방위가 북쪽, 회전이 오른쪽으로 주어졌다면, 노련한 참가자는 남서쪽 모서리를 시작 칸으로 고를 것이며, 번호가 모두 매겨진 정사각형은 다음과 같은 모습이 된다.

주어진 정사각형에서 지정된 직사각형 구역의 내용을 출력하는 프로그램을 작성하여라.

첫째 줄에는 공백 하나로 구분되어 다음이 주어진다: 정사각형 한 변의 길이를 나타내는 정수 $n$ ($2 \le n \le 5000$), 방위를 나타내는 한 단어(POLNOC=북, POLUDNIE=남, ZACHOD=서, WSCHOD=동 중 하나), 허용된 회전을 나타내는 한 단어(PRAWO=오른쪽, LEWO=왼쪽 중 하나).

둘째 줄에는 네 정수 $x_1$, $x_2$, $y_1$, $y_2$ ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$, $(x_2 - x_1)(y_2 - y_1) \le 10^6$)가 주어지며, 각각 출력할 구역의 첫 열과 마지막 열, 첫 행과 마지막 행을 뜻한다. 열은 서쪽에서 동쪽으로 $1$부터 $n$까지, 행은 남쪽에서 북쪽으로 $1$부터 $n$까지 번호가 매겨져 있다.

정확히 $y_2 - y_1 + 1$개의 줄을 출력하고, 각 줄에는 $x_2 - x_1 + 1$개의 수를 공백 하나로 구분하여 출력한다. 이 수들은 번호가 매겨진 정사각형에서 지정된 구역의 각 행을 나타내며, 가장 북쪽 행부터 가장 남쪽 행까지 차례로 출력한다.