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:

Figure 1: Demonstration of how Alice packs the grid on the map

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:

Figure 2: An example of a repetitive path

Figure 3: An example of 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:

Figure 4: The repetitive path after changing the cell at $(3, 3)$ to ‘S’

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.

3 4
WWNW
SWWE
ESEN

0

3 4
SNWS
EENE
WEEN

1
3 3 S