Fishes

A rare species of predatory fish lives in a distant archipelago. Its days are very regular. Every morning a fish wakes up at the same hour and swims out to hunt. In the evening it comes back to the place it set off from and falls asleep there, again at the same hour every day. It can wake up somewhere else, because the currents carry a sleeping fish a little.

Through the whole day a fish keeps one rule: at every moment it has to see the place where it was at the same time on the previous day, exactly 24 hours earlier. A fish cannot see a point lying on the other side of an island.

Ichthyologists watched the archipelago for a long time and every few days they wrote down one route of one fish. After a lot of data had piled up, an accident destroyed part of it and mixed up the rest. The scientists no longer know which fish swam which route. Read the surviving route descriptions and tell them the smallest number of different fish they could have been watching.

The first line contains two integers $w$ and $h$ ($3 \le w \le 1000$, $3 \le h \le 1000$) separated by a single space. Each of the next $h$ lines holds a string of $w$ characters describing one row of the archipelago. The character . is ocean and # is land. Every cell on the border of the map is water.

One point of the archipelago is visible from another if the segment joining them has no common point with the interior or the boundary of any piece of land. The direction in which a fish swims does not matter here.

The next line contains an integer $n$ ($2 \le n \le 1000$), the number of recorded routes. The following $2n$ lines describe them. The first line of a description holds three integers $x$, $y$ and $d$ ($1 \le x \le w$, $1 \le y \le h$, $2 \le d \le 10000$) separated by single spaces, where $x$ and $y$ are the column and the row of the cell in which a fish woke up, and $d$ is the length of the route. The second line is a string of $d$ characters N, W, S, E, the successive directions of the fish, meaning up, left, down and right. Every route runs through water cells only, never leaves the piece of the archipelago given in the input, and ends in the cell where it started.

A fish moves only horizontally or vertically, along the broken line joining the centres of the cells on its way. Its speed is unknown. It can speed up or slow down so that it always sees the point where it was exactly 24 hours earlier.

The currents move a sleeping fish by at most one cell up, down, left or right from the cell in which it fell asleep. You can assume that for every two water cells of the archipelago there is some (hypothetical) fish route passing through both of them.

In the first line write the integer $k$, the smallest number of different fish that agrees with the collected data. In each of the next $k$ lines write the numbers of the routes of a single fish. That fish did not have to swim them on consecutive days, any two days of its life will do.

A fish can swim two routes on two consecutive days if both routes start in the same cell or in cells sharing an edge, and if it can swim the second route while seeing at every moment the point where it was exactly 24 hours earlier.

The routes are numbered from 1 to $n$ in the order they appear in the input. Write the numbers inside a line in increasing order, and order the lines so that their first numbers increase. Both $k$ and this grouping are determined uniquely.

In the sample data the first two routes could belong to one fish, even on two consecutive days. A few days later the same fish could swim the third route. The fourth route belongs to another fish. Unlike the first three, it goes around the big island.