[BalticOI 2000] Electronical Plate

给定一个 $(n-1) \times (n-1)$ 的网格，两条直线的交点有一个节点，则这个网格有 $n \times n$ 个节点，从左往右，从上往下，这些节点依次编号为 $1$ 到 $n^2$。 这些节点中有一些节点被称为「电源」，现在要连一些电路，要求以电源为起点，连向其他节点，要求不能经过其他电源，终点为网格上下左右四个边缘上的节点。 比如说下面这个图，黑色的为电源，白色的为普通节点：  因为有一些电源就在边缘上，我们不需要进行连接。有一种可行解即为：  如果有多组解，找出其中一组即可。

第一行一个整数 $n$ 代表网格的大小。 接下来 $n$ 行每行 $n$ 个整数代表每个节点，$0$ 或者 $1$。 $0$ 代表这个节点是普通节点，$1$ 代表这个节点是电源。

第一行一个整数 $k$ 代表至少需要多少个电源要连电线。（有一些在边缘的电源不需要连电线） 接下来 $k$ 行，每行首先第一个整数代表要连电线的电源的编号，接下来一个字符串代表电源要把电线连向边缘的路线，向左输出 `W`，向右输出 `E`，向上输出 `N`，向下输出 `S`，电源按照编号从小到大输出。 如果有多解，输出一组即可。

6
0 0 0 1 1 1
0 0 0 0 1 0
0 0 0 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 0 0 1 0 1

6
11 E
16 NWN
17 SE
27 S
28 NWWSS
29 S

#### 数据规模与约定 对于 $100\%$ 的数据，$3 \le n \le 15$。 **本题使用 Special Judge。** 感谢 spj 提供者 @[tiger2005](https://www.luogu.com.cn/user/60864)。 #### 说明 翻译自 [BalticOI 2000 Day1 C Electronical Plate](https://boi.cses.fi/files/boi2000_day1.pdf)。