题目描述

译自 ROI 2016 Day1 T2. Экспериментальная робототехника

给一个地图（遵循上北下南左西右东），地图上有 $n$ 行 $m$ 列方格，每个方格中包含 nswe 四者中的其中一个字母。

开始时，有些格子上会有一个机器人，其余格子上没有机器人，并且所有机器人均处于未激活状态。

你可以在时刻 $0\sim 10^9,$ 激活任意多机器人（但激活的机器人不能取消激活）。如果你在时刻 $i$ 激活了某个机器人，在时刻 $i+1,$ 该机器人会根据它刚才（时刻 $i$）所在的方格上的字母，向北/南/西/东移动，移动至相邻格子后停下。在时刻 $i+2,$ $i+3\ldots,$ 机器人会根据它在前一时刻（$i+1,$ $i+2\ldots$）所在的方格上的字母，按照类似方式移动。保证地图上的字母不会使得机器人移出地图边界。

如果两个被激活的机器人在同一时刻处于同一位置（对于不是刚激活的机器人，以移动后的位置为准），则二者会相撞。但是，如果两个机器人在相邻方格，并且“面对面”地移动（也就是交换了位置），二者不视为相撞。如果一个已激活的机器人和一个未激活的机器人在同一时刻处在同一位置，那也不视为相撞。

给出每个方格上的字母，以及哪些方格上开始时有机器人。试求：在时刻 $0\sim 10^9$ 间，你最多能激活多少机器人，使得这些机器人永不相撞。你可能还需要给出方案。

输入格式

第一行：$n,m,g,$ 其中，$g=0$ 或 $1.$ $g=1$ 表示你需要给出方案，反之则不需要。
接下来 $n$ 行，每行 $m$ 个字母，表示地图。输入时为了方便起见，对于开始时有机器人的格子，格子上的小写字母会换成大写字母。

输出格式

第一行：一个整数 $k$，表示最多能激活多少机器人。
如果 $g=1,$ 则接下来 $k$ 行中，每行三个整数 $r,c,t$，分别表示机器人的初始位置和激活时间。
$1 ⩽ r ⩽ n,$ $1 ⩽ c ⩽ m,$ $1 ⩽ t ⩽ 10^9.$

样例 1

input

3 4 0
SSSS
EESW
ENWW

output

4

样例 2

input

3 4 1
SSSS
EeSW
ENwW

output

4
2 3 2
3 2 1
3 4 1
2 1 2

样例 3

input

4 4 1
essS
Eess
Snww
EeWN

output

5
1 4 9
2 1 4
4 3 3
4 1 2
4 4 7

数据范围与提示