题目描述

Bitlandia 是一个大小为 $w\times s$ 的矩形大陆，被划分成 $w\cdot s$ 个 $1\times1$ 的国家。两个国家对应的方格若有公共边，则称它们相邻，每对相邻国家之间都有边境口岸。

Bajtocja 位于坐标 $(1,1)$。苹果只能沿给定的有向边境通道运输。每条允许运输的通道都有一个费用，费用可以为负数；负费用表示运输时反而会获得补贴。

Bajtazar 希望从 Bajtocja 向大陆上所有国家运输苹果，并使总费用尽可能小。题目保证不存在可以通过沿某个回路反复运输而获得无限收益的情况，即图中不存在可达的负环。

对每个国家，求从 $(1,1)$ 运送一吨苹果到该国的最小费用；若无法到达，则输出字母 N。

输入格式

第一行包含三个整数 $w,s,k$：

• $1\le w\le80$；
• $1\le s\le800$；
• $1\le k\le100000$。

接下来 $k$ 行，每行包含两个整数 $a_i,b_i$、一个字符 $c_i$ 和一个整数 $d_i$：

a_i b_i c_i d_i

其中 $1\le a_i\le s$，$1\le b_i\le w$，$c_i\in\{N,E,S,W\}$，$-10000\le d_i\le10000$。

这表示可以从国家 $(a_i,b_i)$ 向方向 $c_i$ 对应的相邻国家运输苹果，费用为 $d_i$。

同一个有序国家对至多出现一次。

输出格式

输出 $w$ 行，每行 $s$ 个值。

第 $i$ 行第 $j$ 个值表示从 $(1,1)$ 到国家 $(j,i)$ 的最小费用。若不可达，则输出 N。

样例输入

3 4 14
1 1 E 5
1 1 N 3
2 1 E 4
4 1 N 2
1 2 E -8
2 2 S 2
2 2 E 3
2 2 N 5
3 2 E -12
4 2 N -6
2 3 W -3
2 3 S -4
2 3 E 10
3 3 E 1

样例输出

0 -3 1 N
3 -5 -2 -14
-3 0 10 -20