Construct the Wall Maze

You must build a maze from a construction kit that consists of:

1. a 6 × 6 grid of unit squares;
2. three walls, each of integer length from 1 to 6, placed either horizontally or vertically to block movement between adjacent squares;
3. one start marker and one end marker.

Coordinates. Columns are numbered 1 to 6 from left to right, and rows are numbered 1 to 6 from top to bottom. A grid corner is given by two integers (x, y), where x is the distance from the left side of the grid (from 0 to 6) and y is the distance from the top side of the grid (from 0 to 6).

Moves. A move goes from one square to an adjacent square that shares an edge with it, as long as the shared edge is not blocked by a wall; you may never leave the grid. The four move directions are:

• N: to the square above (row number decreases by 1);
• S: to the square below (row number increases by 1);
• E: to the square on the right (column number increases by 1);
• W: to the square on the left (column number decreases by 1).

Walls. A horizontal wall of length L lies on some horizontal grid line y and runs from x1 to x1 + L. A vertical wall of length L lies on some vertical grid line x and runs from y1 to y1 + L. A wall may not stick out of the grid. A wall may lie on the outer border of the grid; in that case it separates no squares, but it still counts as a validly placed wall.

A valid maze must satisfy all of the following:

• all three walls are placed;
• no two walls intersect: the only point that two walls may share is a single grid corner that is an endpoint of both of them (overlapping along a segment, crossing each other, or one wall's end touching the middle of another are all forbidden);
• every wall lies inside the grid.

Once the maze is built, a shortest path from the square with the start marker to the square with the end marker is defined; the start square and the end square are different.

In this problem you must do the reverse: given a shortest path of some maze, construct such a maze. The maze must be valid, the given path must be a valid path that leads from the start square to the end square without crossing a wall or leaving the grid, and no shorter valid path (one using fewer moves) may exist.

The input consists of several test cases. The first line of each test case contains three positive integers: the lengths of the three walls (each length is from 1 to 6). The second line contains a string of 1 to 25 characters from N, E, S, W that describes a shortest path from the start marker to the end marker in the maze to be built; each character gives the direction of the next move. Each test case is guaranteed to have at least one solution.

The last test case is followed by a line containing three zeros.

For each test case, print five lines:

1. the column and row number of the square that contains the start marker;
2. the column and row number of the square that contains the end marker;
3. to 5. the positions of the three walls, in the same order as the lengths given in the input.

Each wall position is written as four integers x1 y1 x2 y2: for a horizontal wall its left endpoint followed by its right endpoint, and for a vertical wall its upper endpoint followed by its lower endpoint. Each endpoint is written as its distance from the left side of the grid followed by its distance from the top side of the grid.

A test case may have several valid mazes. Print only the lexicographically smallest one. A maze is represented by the sequence of integers it prints, read from top to bottom and left to right — that is, (start column, start row, end column, end row, then x1 y1 x2 y2 of wall 1, of wall 2, and of wall 3) — and two mazes are compared by comparing these integer sequences lexicographically.