Worm Game Simulation

The game "Worm" is played on a \(50 \times 50\) board where the top-left cell is \((1,1)\). Initially, the worm occupies 20 contiguous squares. The worm starts in a horizontal line from \((25,11)\) to \((25,30)\) with the head at \((25,30)\). At every move, the worm moves one cell in one of the four directions: north (N), south (S), east (E), or west (W). However, the worm cannot move into a cell already occupied by its body (except that the head is allowed to move into the cell that is just vacated by the tail in the same move) and must always remain within the board boundaries.

You will be given a sequence of move commands. Simulate the worm's movement until one of the following occurs:

• The worm collides with itself.
• The worm moves outside the board.
• All commands are successfully executed.

In cases 1 and 2, ignore any remaining commands. After the simulation ends, output the final positions of the worm's cells in order from head to tail.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) representing the number of move commands.
2. The second line contains a string of \(n\) characters. Each character is one of N, S, E, or W, representing a move in the respective direction.

outputFormat

Output exactly 20 lines. Each line should contain two space-separated integers representing the row and column of one cell occupied by the worm, starting with the head and ending with the tail.

sample

0

25 30
25 29
25 28
25 27
25 26
25 25
25 24
25 23
25 22
25 21
25 20
25 19
25 18
25 17
25 16
25 15
25 14
25 13
25 12
25 11