تعيش في مدينة تتقاطع فيها طرق كثيرة تمتد لمسافات طويلة جدًا من الشمال إلى الجنوب مع طرق كثيرة تمتد لمسافات طويلة جدًا من الشرق إلى الغرب. تبلغ المسافة بين كل طريقين متجاورين يمتدان من الشمال إلى الجنوب $1$ كيلومتر، وكذلك المسافة بين كل طريقين متجاورين يمتدان من الشرق إلى الغرب.

يوجد في المدينة مبنى واحد للبلدية. نرمز إلى التقاطع الذي يقع فيه مبنى البلدية بالزوج $(0,0)$. يُمثَّل كل تقاطع في المدينة بالزوج $(i,j)$، حيث $i,j$ عددان صحيحان. أي إن التقاطع $(i,j)$ يقع على بُعد $i$ كيلومتر شرق التقاطع $(0,0)$ (أو $-i$ كيلومتر غربه إذا كان $i<0$)، وعلى بُعد $j$ كيلومتر شماله (أو $-j$ كيلومتر جنوبه إذا كان $j<0$).

تربي البلدية كلبًا اسمه JOI. وضع JOI خطة للتنزه على مدى $K$ أيام، كما يلي:

• في صباح اليوم الأول من الأيام الـ $K$، يكون JOI عند التقاطع $(0,0)$ ويضع علامة عليه. لا توجد علامات وضعها JOI على أي تقاطع آخر.
• يتنزه JOI نهار كل يوم من الأيام الـ $K$. تتكون نزهة اليوم الواحد من $N$ خطوات. في كل خطوة، ينتقل من تقاطع إلى تقاطع مجاور ويضع علامة على التقاطع الذي يصل إليه. يتبع تسلسل الحركات نفسه كل يوم.
• بعد انتهاء حركاته النهارية، ينام عند التقاطع الذي يوجد فيه حتى صباح اليوم التالي.

تتحدث البلدية عن منطقة JOI التي تتكون خلال أيام التنزه الـ $K$. إذا وضع JOI علامة مرة واحدة على الأقل على كل واحد من التقاطعات الأربعة $(a,b)$ و$(a+1,b)$ و$(a+1,b+1)$ و$(a,b+1)$، فإن المربع المحاط بهذه التقاطعات الأربعة ينتمي إلى منطقته.

تقرر أن تكتب برنامجًا يحسب عدد المربعات التي تنتمي إلى منطقة JOI انطلاقًا من خطة تنزهه.

طرق هذه المدينة طويلة جدًا، وعددها كافٍ في الاتجاهين، من الشمال إلى الجنوب ومن الشرق إلى الغرب؛ لذلك لن يصل JOI أثناء تنزهه إلى نهاية طريق أو إلى حدود المدينة.

المهمة

اكتب برنامجًا يحسب عدد المربعات التي تنتمي إلى منطقة JOI، عند إعطائك خطة تنزهه.

الإدخال

اقرأ الإدخال التالي من الإدخال القياسي.

• يحتوي السطر الأول على عددين صحيحين $N,K$ تفصل بينهما مسافة. وهما يعنيان أن نزهة كل يوم تتكون من $N$ خطوات، وأن خطة التنزه تمتد على مدى $K$ أيام.

• يحتوي السطر الثاني على سلسلة $S$ طولها $N$. الحرف $C_p$، وهو الحرف رقم $p$ من اليسار في السلسلة $S$، حيث $1\le p\le N$، هو أحد الأحرف E أو N أو W أو S. تعني هذه الأحرف ما يلي:

  • إذا كان $C_p$ هو E، ينتقل في الخطوة رقم $p$ إلى التقاطع المجاور شرقًا.
  • إذا كان $C_p$ هو N، ينتقل في الخطوة رقم $p$ إلى التقاطع المجاور شمالًا.
  • إذا كان $C_p$ هو W، ينتقل في الخطوة رقم $p$ إلى التقاطع المجاور غربًا.
  • إذا كان $C_p$ هو S، ينتقل في الخطوة رقم $p$ إلى التقاطع المجاور جنوبًا.

بالنسبة إلى التقاطع $(i,j)$، فإن التقاطعات المجاورة شرقًا وشمالًا وغربًا وجنوبًا هي على الترتيب $(i+1,j)$ و$(i,j+1)$ و$(i-1,j)$ و$(i,j-1)$.

الإخراج

اطبع في سطر واحد في الإخراج القياسي عدد المربعات التي تنتمي إلى منطقة JOI.

القيود

تستوفي جميع بيانات الإدخال الشروط التالية:

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

المهام الفرعية

المهمة الفرعية 1 [$5$ نقاط]

تتحقق الشروط التالية:

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

المهمة الفرعية 2 [$10$ نقاط]

• يتحقق $K=1$.

المهمة الفرعية 3 [$23$ نقطة]

• يتحقق $N\le 50$.

المهمة الفرعية 4 [$62$ نقطة]

لا توجد قيود إضافية.

أمثلة

الإدخال 1

12 1
EENWSEEESWWS

الإخراج 1

3

ملاحظة

في هذا المثال، تستغرق النزهة يومًا واحدًا. في اليوم الأول، ينطلق JOI من مبنى البلدية ويتحرك كما في الشكل التالي.

تمثل الدوائر السوداء التقاطعات التي وضع JOI علامات عليها، والدوائر البيضاء التقاطعات التي لم يضع علامات عليها، والدائرة المزدوجة التقاطع الذي يقع فيه مبنى البلدية، والأرقام خطوات الحركة.

مسار حركة JOI

في المثال الأول، تنتمي المربعات الثلاثة المظللة بخطوط مائلة في الشكل التالي إلى منطقة JOI.

منطقة JOI في المثال الأول

الإدخال 2

12 2
EENWSEEESWWS

الإخراج 2

7

ملاحظة

في المثال الثاني، تستغرق النزهة يومين. مسار الحركة في كل يوم هو نفسه في المثال الأول. عند انتهاء النزهة، تنتمي المربعات السبعة المظللة بخطوط مائلة في الشكل التالي إلى منطقة JOI.

منطقة JOI في المثال الثاني

لاحظ أن المثال الثاني لا يستوفي قيود المهمتين الفرعيتين الأولى والثانية.

الإدخال 3

7 1
ENNWNNE

الإخراج 3

0

ملاحظة

في المثال الثالث، لا توجد مربعات تنتمي إلى منطقة JOI.

الإدخال 4

16 5
WSESSSWWWEEENNNW

الإخراج 4

21

ملاحظة

لاحظ أن المثال الرابع لا يستوفي قيود المهمتين الفرعيتين الأولى والثانية.