Vous habitez une ville formée par de nombreuses routes très longues orientées du nord au sud et de l'est à l'ouest. Deux routes nord-sud voisines sont distantes de $1$ km. Il en est de même pour deux routes est-ouest voisines.

Cette ville possède une mairie. Le carrefour où elle se trouve est noté $(0,0)$. Chaque carrefour est représenté par deux entiers $i,j$, sous la forme $(i,j)$. Il s'agit du carrefour situé à $i$ km à l'est de $(0,0)$ (ou $-i$ km à l'ouest si $i<0$) et à $j$ km au nord (ou $-j$ km au sud si $j<0$).

La mairie possède un chien nommé JOI-kun. Il a préparé un programme de promenades sur $K$ jours, comme suit.

• Le matin du premier des $K$ jours, JOI-kun se trouve au carrefour $(0,0)$ et le marque. Aucun autre carrefour ne porte sa marque.
• Chaque jour, il se promène à midi. Une promenade comporte $N$ étapes. À chaque étape, il se déplace d'un carrefour vers un carrefour voisin et marque sa destination. La suite des déplacements effectués à midi est identique tous les jours.
• Après les déplacements de midi, il dort au carrefour où il se trouve jusqu'au lendemain matin.

À la mairie, on discute du territoire que JOI-kun aura constitué après ces $K$ jours. Si les quatre carrefours $(a,b),(a+1,b),(a+1,b+1),(a,b+1)$ ont tous été marqués au moins une fois par JOI-kun, le pâté de maisons qu'ils délimitent appartient à son territoire.

Vous devez écrire un programme qui calcule le nombre de pâtés de maisons appartenant au territoire de JOI-kun à partir de son programme de promenades.

Les routes de la ville sont très longues et suffisamment nombreuses dans les deux directions : pendant ses promenades, JOI-kun n'atteindra jamais l'extrémité d'une route ni la limite de la ville.

Tâche

Écrivez un programme qui, étant donné le programme de promenades de JOI-kun, détermine le nombre de pâtés de maisons appartenant à son territoire.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient deux entiers $N,K$, séparés par une espace. Chaque promenade comporte $N$ étapes et le programme s'étend sur $K$ jours.

• La deuxième ligne contient une chaîne $S$ de longueur $N$. Son caractère $C_p$ en position $p$ depuis la gauche $(1\le p\le N)$ est E, N, W ou S. Ces caractères ont les significations suivantes.

  • Si $C_p$ est E, la $p$-ième étape mène au carrefour voisin situé à l'est.
  • Si $C_p$ est N, la $p$-ième étape mène au carrefour voisin situé au nord.
  • Si $C_p$ est W, la $p$-ième étape mène au carrefour voisin situé à l'ouest.
  • Si $C_p$ est S, la $p$-ième étape mène au carrefour voisin situé au sud.

Pour le carrefour $(i,j)$, les voisins à l'est, au nord, à l'ouest et au sud sont respectivement $(i+1,j)$, $(i,j+1)$, $(i-1,j)$ et $(i,j-1)$.

Sortie

Affichez sur une ligne de la sortie standard le nombre de pâtés de maisons appartenant au territoire de JOI-kun.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Sous-tâche 1 [5 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 2 [10 points]

• $K=1$.

Sous-tâche 3 [23 points]

• $N\le 50$.

Sous-tâche 4 [62 points]

Aucune contrainte supplémentaire.

Exemples

Entrée 1

12 1
EENWSEEESWWS

Sortie 1

3

Remarque

Dans cet exemple, les promenades s'étendent sur un seul jour. Le premier jour, JOI-kun part de la mairie et se déplace comme sur la figure ci-dessous.

Les disques noirs représentent les carrefours marqués, les cercles blancs les carrefours non marqués, le double cercle le carrefour de la mairie, et les nombres indiquent les étapes.

Trajet de JOI-kun

Dans le premier exemple, les trois pâtés de maisons hachurés sur la figure ci-dessous appartiennent au territoire de JOI-kun.

Territoire de JOI-kun dans le premier exemple

Entrée 2

12 2
EENWSEEESWWS

Sortie 2

7

Remarque

Dans le deuxième exemple, les promenades s'étendent sur deux jours. Le trajet de chaque jour est identique à celui du premier exemple. Une fois les promenades terminées, les sept pâtés de maisons hachurés sur la figure ci-dessous appartiennent au territoire de JOI-kun.

Territoire de JOI-kun dans le deuxième exemple

Notez que le deuxième exemple ne satisfait pas les contraintes des sous-tâches 1 et 2.

Entrée 3

7 1
ENNWNNE

Sortie 3

0

Remarque

Dans le troisième exemple, aucun pâté de maisons n'appartient au territoire de JOI-kun.

Entrée 4

16 5
WSESSSWWWEEENNNW

Sortie 4

21

Remarque

Notez que le quatrième exemple ne satisfait pas les contraintes des sous-tâches 1 et 2.