Asut kaupungissa, jossa on monia pitkälle pohjois-eteläsuunnassa jatkuvia teitä ja monia pitkälle itä-länsisuunnassa jatkuvia teitä. Kahden vierekkäisen pohjois-eteläsuuntaisen tien välinen etäisyys on $1\text{ km}$. Vastaavasti kahden vierekkäisen itä-länsisuuntaisen tien välinen etäisyys on $1\text{ km}$.

Tässä kaupungissa on yksi kaupungintalo. Olkoon risteys, jossa kaupungintalo sijaitsee, $(0,0)$. Tämän kaupungin risteys esitetään kahdella kokonaisluvulla $i, j$ muodossa $(i, j)$. Toisin sanoen risteys $(i, j)$ on sijainti, johon päästään liikkumalla $i\text{ km}$ itään (tai $-i\text{ km}$ länteen, jos $i < 0$) ja $j\text{ km}$ pohjoiseen (tai $-j\text{ km}$ etelään, jos $j < 0$) risteyksestä $(0,0)$.

Kaupungintalolla pidetään koiraa nimeltä Joy. Joy on tehnyt suunnitelman kävelylenkeille $K$ päivän ajaksi. Kävelysuunnitelma on seuraava:

• $K$ päivän ensimmäisen päivän aamuna Joy on risteyksessä $(0,0)$. Joy merkitsee risteyksen $(0,0)$. Joy ei ole merkinnyt mitään muuta risteystä kuin $(0,0)$.
• Joy käy kävelyllä päiväsaikaan jokaisena $K$ päivänä. Yhden päivän kävely koostuu $N$ askeleesta. Jokaisella askeleella Joy siirtyy nykyisestä risteyksestä viereiseen risteykseen ja merkitsee määränpään. Se, miten Joy liikkuu päivän aikana, on sama joka päivä.
• Kun päivän liikkuminen on päättynyt, Joy nukkuu nykyisessä risteyksessä seuraavan päivän aamuun asti.

Kaupungintalolla keskustellaan Joyn reviiristä, joka syntyy $K$ päivän kävelyistä. Neljän risteyksen $(a,b), (a+1,b), (a+1,b+1), (a,b+1)$ rajaama alue kuuluu Joyn reviiriin, jos Joy on merkinnyt kaikki nämä neljä risteystä vähintään kerran.

Tehtäväsi on kirjoittaa ohjelma, joka laskee Joyn reviiriin kuuluvien alueiden lukumäärän Joyn kävelysuunnitelman perusteella.

Koska tämän kaupungin tiet ovat hyvin pitkiä ja teitä on riittävän monta sekä pohjois-etelä- että itä-länsisuunnassa, Joy ei koskaan saavuta tien päätä tai kaupungin reunaa kävelyjen aikana.

Syöte

Lue seuraava syöte standardisyötteestä:

• Ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $K$. Tämä ilmaisee, että jokaisen päivän kävely koostuu $N$ askeleesta ja kävelysuunnitelma kattaa $K$ päivää.
• Toinen rivi sisältää pituudeltaan $N$ olevan merkkijonon $S$. Merkkijonon $S$ vasemmalta lukien $p$-s merkki $C_p$ ($1 \le p \le N$) on jokin merkeistä 'E', 'N', 'W', 'S'. Nämä merkit tarkoittavat seuraavaa:
  • Jos merkki $C_p$ on 'E', se tarkoittaa siirtymistä idässä olevaan risteykseen $p$-nnellä askeleella.
  • Jos merkki $C_p$ on 'N', se tarkoittaa siirtymistä pohjoisessa olevaan risteykseen $p$-nnellä askeleella.
  • Jos merkki $C_p$ on 'W', se tarkoittaa siirtymistä lännessä olevaan risteykseen $p$-nnellä askeleella.
  • Jos merkki $C_p$ on 'S', se tarkoittaa siirtymistä etelässä olevaan risteykseen $p$-nnellä askeleella.

Tässä risteykselle $(i, j)$ idässä, pohjoisessa, lännessä ja etelässä olevat risteykset ovat vastaavasti $(i+1, j)$, $(i, j+1)$, $(i-1, j)$ ja $(i, j-1)$.

Tuloste

Tulosta Joyn reviiriin kuuluvien alueiden lukumäärä standarditulosteeseen yhdellä rivillä.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

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

Osatehtävät

Osatehtävä 1 [5 pistettä]

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

Osatehtävä 2 [10 pistettä]

• $K = 1$.

Osatehtävä 3 [23 pistettä]

• $N \le 50$.

Osatehtävä 4 [62 pistettä]

• Ei lisärajoituksia.

Esimerkit

Syöte 1

12 1
EENWSEEESWWS

Tuloste 1

3

Huomautus

Tässä esimerkissä kävely suoritetaan 1 päivän ajan. Ensimmäisenä päivänä Joy lähtee kaupungintalolta ja liikkuu alla olevan kuvan mukaisesti. Mustat ympyrät ovat Joyn merkitsemiä risteyksiä, valkoiset ympyrät ovat risteyksiä, joita Joy ei ole merkinnyt, kaksoisympyrä on risteys, jossa kaupungintalo sijaitsee, ja numerot esittävät kutakin askelta.

Joyn kulkureitti

Esimerkissä 1 alla olevassa kuvassa varjostetulla alueella osoitetut 3 aluetta kuuluvat Joyn reviiriin.

Joyn reviiri esimerkissä 1

Syöte 2

12 2
EENWSEEESWWS

Tuloste 2

7

Huomautus

Esimerkissä 2 kävely suoritetaan 2 päivän aikana. Jokaisen päivän kulkureitti on sama kuin esimerkissä 1. Kun kävely on suoritettu, alla olevassa kuvassa varjostetulla alueella osoitetut 7 aluetta kuuluvat Joyn reviiriin.

Joyn reviiri esimerkissä 2

Syöte 3

7 1
ENNWNNE

Tuloste 3

0

Huomautus

Esimerkissä 3 ei ole yhtään aluetta, joka kuuluisi Joyn reviiriin.

Syöte 4

16 5
WSESSSWWWEEENNNW

Tuloste 4

21