题目描述

小 H 闲来无事，于是决定养鱼。

小 H 的鱼的生活区域是一个矩形，被分成了 $h\times w$ 个 $1\times 1$ 的格子。其中有一些格子是障碍，剩下的格子是空地。保证任意两个空地之间都可以在不经过障碍的前提下，通过上下左右移动互相到达。

鱼很喜欢运动。每一天，一条鱼会从一个点 $(x,y)$ 出发，不断上下左右移动，最后回到出发点。在这个过程中，鱼只能经过空地，不能碰到障碍。

在鱼结束一天的行程后，它会睡觉。睡觉时由于水在流动，第二天这条鱼的出发点可能是一个与前一天的出发点相邻的格子，也可能保持不变。

由于受到宇宙射线的影响，鱼很不放心自己的安全，因此鱼的行动路径需要满足一个特殊条件。

对于一天中的任意一个时刻，设鱼今天在当前时刻处于位置 $(x_0,y_0)$，上一天在同一时刻处于位置 $(x_1,y_1)$，则方格 $(x_0,y_0)$ 与 $(x_1,y_1)$ 的中心点之间的连线不能经过任何障碍。

称一条线段经过某个障碍，当且仅当它与该障碍格区域的交集长度大于 $0$；若它不经过任何障碍，则称该线段没有经过障碍。原题下发文件中给出了一张示意图：两个红点之间的连线经过了一个障碍，而两个蓝点之间的连线没有经过任何障碍。

注意，在鱼睡觉时，水流对它的影响不一定要满足上述限制。

鱼的速度是任意的：它既可以以极快的速度向前移动，也可以在原地停留很长时间，还可以在任意时刻任意改变自己的速度。但鱼的运动必须是连续的。也就是说，当鱼从 $(x,y)$ 移动到 $(x',y')$ 时，不是直接跳过去，而是沿着方格 $(x,y)$ 和 $(x',y')$ 的中心点之间的线段连续运动。

小 H 会时不时观察这些鱼，并在某些天选择一些鱼，记录下它们运动的路径。

现在你看到了小 H 的记录，共有 $n$ 条，但这些记录已经被打乱。你想知道小 H 至少养了多少条鱼，才可能产生这些记录。

换句话说，你需要求出最小的 $k$，使得存在一种将这 $n$ 条记录分成 $k$ 组的方式，并且对于每一组，都可以重新排列其中的记录，使它们能够作为同一条鱼在某些天的运动轨迹。

这些天不一定连续。例如，如果一条鱼能够在第 $1,50,100,10^{100}$ 天分别走出某 $4$ 条运动轨迹，那么这 $4$ 条记录可以被分在同一组中。

为了证明你的答案不是猜测，你还需要输出一种分组方案。

输入格式

第一行包含两个正整数 $w,h$，分别表示矩形区域的宽度和高度。

接下来 $h$ 行，每行包含 $w$ 个字符，描述矩形区域的地图：

• . 表示空地；
• # 表示障碍。

下一行包含一个整数 $n$，表示记录的数量。

接下来 $2n$ 行依次描述这 $n$ 条记录。每条记录占两行：

• 第一行包含三个整数 $y,x,l$，表示这条记录中鱼的起点为第 $x$ 行第 $y$ 列，运动轨迹的长度为 $l$；
• 第二行包含一个长度为 $l$ 的字符串，表示运动轨迹，其中：
  • N 表示向上一格；
  • S 表示向下一格；
  • W 表示向左一格；
  • E 表示向右一格。

保证每条路径只经过空地，并且最终回到出发点。

不保证路径不经过重复的格子。

输出格式

第一行输出一个整数 $k$，表示最少可能的鱼的数量。

接下来输出 $k$ 行。每行输出若干个整数

$$i_1,i_2,\ldots,i_s,$$

表示输入中的第 $i_1,i_2,\ldots,i_s$ 条记录可以由同一条鱼走出。

同一行中的记录编号必须按照从小到大的顺序输出，不是按照鱼实际走出这些轨迹的时间顺序输出。

这 $k$ 行之间按照每行的第一个编号 $i_1$ 从小到大排列。

可以证明，输出方案是唯一的。

样例 1

输入

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

输出

2
1 2 3
4

样例解释

前两条记录可以在连续两天由同一条鱼走出。这条鱼在若干天之后，还可以走出第三条记录。

但第四条记录绕着一块障碍物走了一圈，因此不可能与前三条记录由同一条鱼走出。

数据范围与子任务

对于全部测试数据：

$$1\le h,w,n\le 10^3,$$ $$1\le x\le h,\qquad 1\le y\le w,\qquad 1\le l\le 10^4.$$

子任务	分值	限制
1	10	$1\le h,w\le 5$，$n\le 100$
2	20	输入中至多有一个 # 字符
3	40	$1\le n\le 100$
4	30	无附加限制