Problem C
Inspeção de Esteiras

Uma empresa que fabrica esteiras transportadoras mantém $n \cdot m$ esteiras em um galpão que pode ser representado por uma matriz de $n$ linhas e $m$ colunas. Cada esteira ocupa exatamente uma posição da matriz e pode estar virada para o norte (N), sul (S), leste (E) ou oeste (W).

Se um objeto está na posição $(i, j)$ da matriz em $1$ segundo estará na posição $(i-1, j)$ se a esteira na posição inicial aponta para o norte, $(i+1, j)$ se aponta para o sul, $(i, j-1)$ se aponta para o leste e $(i, j+1)$ se aponta para o oeste. Note que essa nova posição pode estar fora da matriz, nesse caso o objeto sai dela.

João está estagiando como inspetor de esteiras e precisa inspecionar todas as esteiras que ele tem. Como é seu primeiro estágio, João não faz ideia do que está fazendo e decide coletar dados insignificantes para avaliar uma esteira.

Vamos chamar de $f(x)$ o tempo em segundos que um objeto colocado na esteira $x$ demora até sair da matriz ou visitar uma esteira que ele já visitou anteriormente. João quer saber a soma de $f(x)$ para todas as esteiras.

João é muito preguiçoso e não se deu ao trabalho nem de simular o processo nem de escrever um programa que simula. Ajude João a encontrar o valor que precisa.

Input

A primeira linha do input contém dois inteiros, $n$ e $m$ ($1 \leq n, m \leq 10^3$), o número de linhas e o número de colunas da matriz, respectivamente.

Seguirão $n$ linhas. A $i$-ésima linha contém $m$ letras. A $j$-ésima letra pode ser N, S, E ou W, e representa a direção em que a esteira na posição $(i, j)$ está apontando.

Output

Imprima um único inteiro, a soma de $f(x)$ para todas as $n \times m$ esteiras.

1 3
WWW

6

3 3
EES
NNS
NWW

73

3 3
ESN
NWW
NNW

38