在方形板的顶部刻有一个方形网格。两条网格线交叉的地方称为节点。网格中共有 $n \times n$ 个节点。

图 2. 问题（中）与解（右）

某些节点上包含引脚。任务是使用电子电路将这些引脚连接到板的边界节点上。电路只能沿网格铺设（例如，不能斜向铺设）。任意两条电路不能有公共点，因此任意两条电路不能铺设在同一条网格线上，也不能铺设在同一个节点上。电路不能铺设在边界网格上（电路一旦到达边界就必须结束），也不能铺设在包含另一个引脚的节点上。

图 2 中间展示了一个包含引脚的电子板示例。图中的黑点代表引脚。

编写一个程序，将尽可能多的引脚连接到边界节点上。已经在边界上的引脚已经满足要求，无需为它们制作电路。

如果存在多个解，请找出其中任意一个。

输入格式

输入的第一行包含一个整数 $n$ ($3 \le n \le 15$)。

接下来的 $n$ 行，每行包含 $n$ 个由空格分隔的数字。数字可以是 1 或 0。1 表示引脚，0 表示网格中相应位置没有引脚的节点。

节点从 $1$ 到 $n \times n$ 进行编号，首先从左到右，然后从上到下（行优先顺序）。引脚所在的节点编号即为该引脚的标识符。

输出格式

在第一行输出 $k$ —— 使用电子电路连接到边界的引脚的最大数量。

在接下来的 $k$ 行中，每行描述一条连接相应引脚到边界的电路。首先是引脚的标识符，然后是描述电路方向的字母序列：E - 向东，W - 向西，N - 向北，S - 向南。标识符和字母序列之间应留有一个空格，序列中的字母之间不应留有空格。

结果应按引脚标识符的升序排列。

样例

样例输入 1

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

样例输出 1

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