# Problem J

Journey of the Repetitor

After watching the novel “Around the World in Eighty Days”, Alice becomes enthusiastic in travelling abroad. However, due to the lack of flights during the COVID-19 pandemic, Alice decides to travel around the world on foot!

However, Alice is suffering from decidophobia, so she is
unable to decide how to travel around the world. Hence, she
develops an innovative method for generating her path: she
randomly generates a grid with size $n \times m$, with each cell
containing an arrow pointing one of the four directions (north,
east, south or west). Then, she packs the grid infinitely many
times on the map **without rotation**. The
following figure shows what the map looks like after packing
the grid:

It is known that the initial position of Alice matches the top-left corner of the grid. After packing the grids on the map, she starts moving on the map according to the direction of the arrows. Once she reaches another cell, she will continue moving according to the arrow on that new cell. She never stops moving.

When Alice draws her journey on the map, she discovers that
some grids may lead to a *infinite* path:
none of the cells she visits will be visited infinitely many
times. She doesn’t like infinite paths as these paths will
often lead to a lonely and boring experience. She likes
*repetitive* paths instead: some of the
cells she visits will be visited infinitely many times. The
figures below shows an example of a repetitive path and an
infinite path:

Alice plans to change some of the cells in her grid so that the path will become repetitive. Once she changes a cell in the grid, all occurrences of the cell in the map will be changed. For example, the infinite path in the figure above can be made repetitive by changing the cell at $(3, 3)$ to ‘S’. The new map is shown below:

Can you help Alice to determine the **minimum number of cells** she needs to change in
order to make the path repetitive?

## Input

The first line of input contains two integers $n$ and $m$ ($2 \leq n, m \leq 3000$).

The next $n$ lines of input each contains $m$ characters, the cells on the grid (‘N’ for north, ‘E’ for east, ‘S’ for south, ‘W’ for west).

## Output

Output the minimum number of changes made to the grid, $k$, on the first line.

The next $k$ lines should each contain a change, denoted by 2 integers representing the position (row & column) followed by a character (the edited direction of that cell, either ‘N’, ‘E’, ‘S’ or ‘W’). You may output the cells in any order.

The row and column numbers are 1-indexed.

If there are multiple solutions, you may output any of them.

Sample Input 1 | Sample Output 1 |
---|---|

3 4 WWNW SWWE ESEN |
0 |

Sample Input 2 | Sample Output 2 |
---|---|

3 4 SNWS EENE WEEN |
1 3 3 S |