Dyeing Dice

You have opened a factory that colours the six faces of a plain wooden die. The factory floor is a board of size $N \times N$. Some of the $N^2$ squares hold paint and the rest hold nothing. The square in the south west corner is $(1, 1)$, the square in the north west corner is $(1, N)$, the square in the north east corner is $(N, N)$, and the square in the south east corner is $(N, 1)$. The square $(1, 1)$ never holds paint.

The die is coloured by rolling it along a path that is fixed in advance. When the die lands on a square that holds paint, the face touching that square takes the colour of the paint. When the die lands on a square with no paint, nothing happens. The die is finished the moment all six faces are coloured, and it is taken out of the factory at that moment, so the rest of the path is ignored.

The die starts on square $(1, 1)$ with the number 1 facing up and the number 2 facing square $(2, 1)$. The number 6 is then on the bottom, the number 3 faces square $(1, 2)$, the number 4 faces the south side of the board, and the number 5 faces the west side of the board. Two opposite faces of a die always add up to 7.

The die can be rolled one square at a time in four directions: N, S, E and W. The faces tip over as it rolls. Rolling north from the starting position puts the die on square $(1, 2)$ with the number 4 facing up and the number 6 facing south. Rolling east from the starting position puts the die on square $(2, 1)$ with the number 5 facing up and the number 4 facing south.

Three things can go wrong while the die is being coloured. The die can roll off the board. The path can end before all six faces are coloured. An already coloured face can land on paint of a different colour, which mixes the paint and is not allowed. An already coloured face landing on paint of the same colour is fine.

The first line holds three integers $N$, $M$ and $P$: the size of the board ($2 \le N \le 200$), the number of squares that hold paint ($1 \le M < N^2$), and the length of the path ($1 \le P \le 100000$).

Each of the next $M$ lines holds three integers $x$, $y$ and $t$, meaning that square $(x, y)$ holds colour $t$. Here $1 \le x, y \le N$ and $1 \le t \le 100$. Every line names a different square, and none of them is $(1, 1)$.

The last line holds a string of length $P$ made of the letters N, S, E and W. This is the path the die is rolled along. N means one roll to the north, S one roll to the south, E one roll to the east, and W one roll to the west.

Print six integers on one line: the colours of the six faces in order, starting with the colour of the face numbered 1 and ending with the colour of the face numbered 6. If the die is not coloured correctly, print 0 0 0 0 0 0 instead.