Vives en una ciudad formada por muchas calles muy largas que se extienden de norte a sur y muchas otras que se extienden de este a oeste y se cruzan con las primeras. La distancia entre dos calles consecutivas que van de norte a sur es de 1 km. La distancia entre dos calles consecutivas que van de este a oeste también es de 1 km.

La ciudad tiene un ayuntamiento. Denotamos por $(0,0)$ la intersección donde se encuentra. Cada intersección de la ciudad se representa como $(i,j)$ mediante dos enteros $i,j$. Es decir, la intersección $(i,j)$ se encuentra a $i$ km al este de $(0,0)$ (o $-i$ km al oeste si $i<0$) y a $j$ km al norte (o $-j$ km al sur si $j<0$).

En el ayuntamiento cuidan de un perro llamado ジョイ君. ジョイ君 ha preparado un plan de paseos de $K$ días, que es el siguiente.

• La mañana del primer día de los $K$ días, ジョイ君 está en la intersección $(0,0)$ y la marca. No hay ninguna otra intersección marcada por él.
• Durante el día, en cada uno de los $K$ días, sale a pasear. Cada paseo consta de $N$ pasos. En cada paso se mueve de una intersección a otra adyacente y marca la intersección de destino. La secuencia de movimientos que realiza durante el día es la misma todos los días.
• Después de terminar los movimientos del día, duerme en la intersección donde se encuentra hasta la mañana siguiente.

En el ayuntamiento se habla del territorio que ジョイ君 habrá formado tras los paseos de los $K$ días. Si ha marcado al menos una vez cada una de las cuatro intersecciones $(a,b),(a+1,b),(a+1,b+1),(a,b+1)$, la manzana delimitada por ellas pertenece a su territorio.

Se te ha encargado escribir un programa que calcule, a partir del plan de paseos de ジョイ君, cuántas manzanas pertenecen a su territorio.

Las calles de esta ciudad son muy largas y hay suficientes calles tanto de norte a sur como de este a oeste, de modo que ジョイ君 nunca llegará al final de una calle ni al límite de la ciudad durante los paseos.

Tarea

Dado el plan de paseos de ジョイ君, escribe un programa que calcule el número de manzanas que pertenecen a su territorio.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene dos enteros $N,K$ separados por un espacio. Indican que cada paseo consta de $N$ pasos y que el plan abarca $K$ días.

• La segunda línea contiene una cadena $S$ de longitud $N$. Su carácter $p$-ésimo desde la izquierda ($1\le p\le N$), $C_p$, es uno de E, N, W, S. Estos caracteres significan lo siguiente.

  • Si $C_p$ es E, en el paso $p$ se mueve a la intersección adyacente al este.
  • Si $C_p$ es N, en el paso $p$ se mueve a la intersección adyacente al norte.
  • Si $C_p$ es W, en el paso $p$ se mueve a la intersección adyacente al oeste.
  • Si $C_p$ es S, en el paso $p$ se mueve a la intersección adyacente al sur.

Las intersecciones adyacentes al este, norte, oeste y sur de $(i,j)$ son, respectivamente, $(i+1,j)$, $(i,j+1)$, $(i-1,j)$ y $(i,j-1)$.

Salida

Escribe en una línea de la salida estándar el número de manzanas que pertenecen al territorio de ジョイ君.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

• $1\le N\le 100\,000$.
• $1\le K\le 1\,000\,000\,000$.

Subtareas

Subtarea 1 [5 puntos]

Se cumplen las siguientes condiciones.

• $N\le 50$.
• $K=1$.

Subtarea 2 [10 puntos]

• $K=1$.

Subtarea 3 [23 puntos]

• $N\le 50$.

Subtarea 4 [62 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

12 1
EENWSEEESWWS

Salida 1

3

Nota

En este ejemplo, los paseos duran un solo día. El primer día, ジョイ君 parte del ayuntamiento y se mueve como se muestra en la figura siguiente.

Los círculos negros indican las intersecciones que ha marcado; los círculos blancos, las que no ha marcado; el círculo doble indica la intersección donde está el ayuntamiento, y los números indican cada paso.

Recorrido de ジョイ君

En el ejemplo 1, las tres manzanas rayadas de la figura siguiente pertenecen al territorio de ジョイ君.

Territorio de ジョイ君 en el ejemplo 1

Entrada 2

12 2
EENWSEEESWWS

Salida 2

7

Nota

En el ejemplo 2, los paseos se realizan durante dos días. El recorrido de cada día es el mismo que en el ejemplo 1. Al terminar los paseos, las siete manzanas rayadas de la figura siguiente pertenecen al territorio de ジョイ君.

Territorio de ジョイ君 en el ejemplo 2

Ten en cuenta que el ejemplo 2 no cumple las restricciones de las subtareas 1 y 2.

Entrada 3

7 1
ENNWNNE

Salida 3

0

Nota

En el ejemplo 3 no hay ninguna manzana que pertenezca al territorio de ジョイ君.

Entrada 4

16 5
WSESSSWWWEEENNNW

Salida 4

21

Nota

Ten en cuenta que el ejemplo 4 no cumple las restricciones de las subtareas 1 y 2.