주사위 염색

나무로 만든 주사위의 여섯 면에 색을 입히는 공장을 열었다. 공장 바닥은 $N \times N$ 크기의 판이고, $N^2$개의 칸 중 일부에는 물감이 깔려 있고 나머지 칸에는 아무것도 없다. 남서쪽 구석 칸이 $(1, 1)$, 북서쪽 구석 칸이 $(1, N)$, 북동쪽 구석 칸이 $(N, N)$, 남동쪽 구석 칸이 $(N, 1)$이다. $(1, 1)$에는 물감이 깔려 있지 않다.

주사위는 미리 정해 둔 경로를 따라 굴려서 색을 입힌다. 물감이 깔린 칸에 주사위가 놓이면 그 칸에 닿은 면이 물감 색으로 물든다. 물감이 없는 칸에 놓이면 아무 일도 일어나지 않는다. 여섯 면이 모두 물든 순간 주사위를 공장에서 꺼내므로, 경로에 남은 이동은 무시한다.

주사위는 $(1, 1)$에서 시작한다. 처음에는 1이 위를 향하고 2가 $(2, 1)$ 칸 쪽을 향한다. 그러면 6은 바닥에 있고, 3은 $(1, 2)$ 칸 쪽을, 4는 판의 남쪽 바깥을, 5는 판의 서쪽 바깥을 향한다. 주사위에서 마주 보는 두 면에 적힌 수의 합은 항상 7이다.

주사위는 북, 남, 동, 서 네 방향으로 한 칸씩 굴릴 수 있고, 굴릴 때마다 면이 넘어간다. 시작 위치에서 북쪽으로 굴리면 주사위는 $(1, 2)$에 놓이고 4가 위를, 6이 남쪽을 향한다. 시작 위치에서 동쪽으로 굴리면 주사위는 $(2, 1)$에 놓이고 5가 위를, 4가 남쪽을 향한다.

색을 입히다가 잘못될 수 있는 경우는 세 가지다. 주사위가 판 밖으로 굴러 나갈 수 있다. 여섯 면을 다 물들이기 전에 경로가 끝날 수 있다. 이미 물든 면이 다른 색 물감 위에 놓일 수 있는데, 이러면 색이 섞이므로 허용하지 않는다. 이미 물든 면이 같은 색 물감 위에 놓이는 것은 괜찮다.

첫째 줄에 세 정수 $N$, $M$, $P$가 주어진다. $N$은 판의 크기 ($2 \le N \le 200$), $M$은 물감이 깔린 칸의 수 ($1 \le M < N^2$), $P$는 경로의 길이 ($1 \le P \le 100000$)다.

다음 $M$개의 줄에는 각각 세 정수 $x$, $y$, $t$가 주어진다. $(x, y)$ 칸에 색 $t$의 물감이 깔려 있다는 뜻이며, $1 \le x, y \le N$이고 $1 \le t \le 100$이다. 각 줄은 서로 다른 칸을 가리키고, 그중 $(1, 1)$은 없다.

마지막 줄에는 N, S, E, W로 이루어진 길이 $P$의 문자열이 주어진다. 주사위를 굴릴 경로이며, N은 북쪽으로 한 칸, S는 남쪽으로 한 칸, E는 동쪽으로 한 칸, W는 서쪽으로 한 칸 굴린다는 뜻이다.

한 줄에 여섯 면의 색을 정수 여섯 개로 출력한다. 1이 적힌 면의 색부터 6이 적힌 면의 색까지 번호 순서대로 쓴다. 주사위에 제대로 색을 입히지 못했다면 0 0 0 0 0 0을 출력한다.