Klasy

In Byteotia, children play an interesting variant of hopscotch (called klasy in Polish). A square with side $n$ is painted on the pavement, divided into $n^2$ identical cells. The task of one of the children, hereafter called the player, is to number all the cells according to a strict rule. Before the game the player is assigned a cardinal direction (north, south, west, or east) and an allowed turn (right or left).

The player steps onto one of the four corner cells of the square, faces the assigned direction, and starts numbering by writing $1$ on the starting cell. On each move the player:

• steps one cell forward, but only if after the move they are still inside the square and the target cell is free (not yet numbered);
• otherwise turns exactly once in the allowed direction and then steps one cell forward.

The player writes the next natural number on each newly visited cell. In addition, on the very first move the player may not turn and must go straight in the assigned direction, so the starting cell has to be chosen carefully. For example, if the square has side $5$, the direction is north and the turn is right, an experienced player would choose the south-west corner as the starting cell, and the fully numbered square would look like this:

Your task is to write a program that prints the contents of a given rectangular fragment of the filled-in square.

The first line of input contains, separated by single spaces: an integer $n$ ($2 \le n \le 5000$) denoting the side length of the square, one word denoting the cardinal direction (one of POLNOC=north, POLUDNIE=south, ZACHOD=west, WSCHOD=east), and one word denoting the allowed turn (one of PRAWO=right, LEWO=left).

The second line contains four integers $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$), denoting respectively the first and last column and the first and last row of the fragment to print. Columns are numbered from $1$ to $n$ from west to east, and rows from $1$ to $n$ from south to north.

Print exactly $y_2 - y_1 + 1$ lines, each containing $x_2 - x_1 + 1$ numbers separated by single spaces. They represent the successive rows of the requested fragment of the numbered square, listed in order from the northernmost row to the southernmost.