在遥远的群岛上，生活着一种稀有的掠食性鱼类。它们的生活节奏非常有规律。每条鱼每天早上都在同一时间醒来并开始捕猎。傍晚时分，它会回到出发的地方并在那里睡觉（每天都在同一时间），但由于洋流的轻微推动，它第二天醒来的位置可能会有所不同。

在整整一天中，鱼必须遵循以下规则：在任何时刻，它都必须能看到它在前一天同一时刻（即恰好 24 小时前）所在的位置。当然，鱼无法看到位于某个岛屿另一侧的点。

鱼类学家对群岛上的鱼类进行了长时间的观察，每隔几天就会记录下某条鱼的一条路线。不幸的是，在收集了大量数据后发生了一起事故。部分数据丢失了，其余的数据也完全混乱。科学家们甚至不知道每条记录的路线分别属于哪条鱼。他们向你寻求帮助。他们将提供混乱的鱼类路线描述，并要求你计算出在他们的研究中观察到的不同鱼类的最小数量。

输入格式

你的程序应从标准输入读取数据。输入由两部分组成：群岛的描述和鱼类路线的描述。群岛描述的第一行包含两个整数 $w$ 和 $h$ ($3 \le w \le 1\,000$, $3 \le h \le 1\,000$)，由一个空格分隔。接下来的 $h$ 行中，每行包含一个长度为 $w$ 的字符串，描述了群岛的一部分。字符 '.' 代表海洋，'#' 代表陆地。地图边界上的所有单元格均为水域（'.' 字符）。

如果连接两个点的线段与任何陆地的内部或边界没有公共点，则称群岛中的一个点对另一个点可见。鱼游动的方向在此处不重要。

下一行包含一个整数 $n$ ($2 \le n \le 1\,000$)，即记录的鱼类路线数量。接下来的 $2n$ 行包含这些路线的描述。路线描述的第一行包含三个整数 $x$、$y$ 和 $d$ ($1 \le x \le w$, $1 \le y \le h$, $2 \le d \le 10\,000$)，由空格分隔。$x$ 和 $y$ 是鱼醒来位置的坐标（列和行），$d$ 是路线的长度。第二行是一个长度为 $d$ 的字符串，由 'N'、'W'、'S' 或 'E' 组成，分别代表向上、向左、向下和向右的移动方向。保证路线仅经过水域单元格，鱼不会离开输入中描述的群岛片段，且每条路线的起点和终点都在同一个单元格。

鱼只能水平或垂直移动；它沿着连接路径上单元格中心的折线游动。然而，我们不知道它的速度。鱼可以加速或减速，以便始终能看到它 24 小时前所在的位置。

洋流可以将正在睡觉的鱼从它入睡的位置最多移动一个单元格（上、下、左或右）。你可以假设，对于群岛中的任意两个水域单元格，都存在某条（假设的）鱼类路线经过这两个单元格。

输出格式

在标准输出的第一行，你的程序应输出一个整数 $k$，即符合科学家收集的数据的最小可能不同鱼类数量。接下来的 $k$ 行，每行应包含一条鱼的路线列表。鱼不一定需要在连续的几天内游完这些路线，而是在其生命中的任意两天。

如果两条路线的起点在相同或相邻的单元格（共享边的单元格），并且鱼在游完第二条路线时始终能看到它 24 小时前所在的位置，那么这条鱼就可以在连续的两天内游完这两条路线。

路线根据输入中的顺序从 $1$ 到 $n$ 进行编号。输出中每一行的路线编号应按升序排列，且各行应按每行第一个数字构成的序列的升序进行排序。

样例

输入 1

10 8
..........
.......#..
........#.
..........
...#......
......###.
......###.
..........
4
2 7 12
NNNEEESSSWWW
2 8 24
WNNNNNNNEEEEESSSSSSSWWWW
1 8 46
NNNNNNNEEEEESSSSSSSEEEENNNNNNNSSSSSSSWWWWWWWWW
1 8 32
NNNNNNNEEEEEEEEESSSSSSSWWWWWWWWW

输出 1

2
1 2 3
4

说明

前两条路线可能是同一条鱼游过的（甚至是在连续的两天内）。几天后，这条鱼可能游过了第三条路线。然而，最后一条路线一定是由另一条鱼游过的。与前三条路线不同，它绕过了大岛。