האם אתם מכירים את Just Odd Inventions Co., Ltd.? עיסוקה של החברה הוא ביצוע ״המצאות מוזרות בלבד״. כאן נקרא לה בקיצור חברת JOI.

חברת JOI פיתחה נגיף חדש בשם ״JOI Virus״. החברה רוצה לערוך ניסוי באמצעות הדבקת תושבי האי IOI בנגיף JOI Virus.

האי IOI הוא מלבני. יש בו $R-1$ כבישים מקבילים ממזרח למערב ו־$C-1$ כבישים מקבילים מצפון לדרום. הם מחלקים את האי ל־$RC$ אזורים. בכל אזור מתגורר תושב אחד בדיוק. לתושב המתגורר באזור ה־$i$ מצפון וה־$j$ ממערב ($1\le i\le R$, $1\le j\le C$) נקרא ״תושב $(i,j)$״.

באי IOI יש $M$ פרקי זמן בכל יום. לפרק הזמן ה־$k$ נקרא ״פרק זמן $k$״. תמיד נושבת רוח מאחד הכיוונים צפון, דרום, מזרח או מערב. הכיוון עשוי להשתנות בהתאם לפרק הזמן. באותו פרק זמן הרוח נושבת מאותו כיוון בכל יום.

לכל תושב יש תכונה הנקראת ״עמידות״. העמידות של תושב $(i,j)$ ($1\le i\le R$, $1\le j\le C$) מיוצגת במספר שלם אי־שלילי $U_{i,j}$.

• אם $U_{i,j}=0$, לתושב $(i,j)$ יש עמידות גבוהה והוא אינו נדבק בנגיף JOI Virus.

• אם $U_{i,j}$ הוא מספר שלם חיובי, תושב $(i,j)$ עלול להידבק בנגיף JOI Virus. אם התנאי הבא מתקיים ברציפות במשך $U_{i,j}$ פרקי זמן, התושב יידבק החל מפרק הזמן הבא:

  • התושב המתגורר באזור הסמוך בכיוון שממנו נושבת הרוח כבר נגוע בנגיף JOI Virus.

  שימו לב שפרק הזמן האחרון של יום ופרק הזמן הראשון של היום הבא רציפים זה לזה.

לצורך הניסוי אנו רוצים להדביק לפחות תושב אחד, אך איננו רוצים להדביק תושבים רבים מדי. בתחילה בוחרים תושב אחד כנדבק הראשון ומדביקים אותו בנגיף JOI Virus. אי אפשר לבחור תושב שעמידותו $0$ כנדבק הראשון.

נתונים כיוון מקור הרוח בכל פרק זמן ועמידותו של כל תושב. כתבו תוכנית המחשבת את המספר המזערי של תושבים נגועים לאחר $10^{100}$ ימים, ואת מספר התושבים שבחירתם כנדבק הראשון משיגה מספר מזערי זה.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

$$ \begin{array}{lll} M&R&C\\ D\\ U_{1,1}&\cdots&U_{1,C}\\ \vdots&&\vdots\\ U_{R,1}&\cdots&U_{R,C} \end{array} $$

$D$ היא מחרוזת באורך $M$ המציינת את הכיוון שממנו נושבת הרוח באי IOI. המחרוזת מורכבת מארבעה סוגי תווים: N, S, W או E. התו ה־$k$ ($1\le k\le M$) מציין את הכיוון שממנו נושבת הרוח בפרק זמן $k$. שימו לב שזהו אינו הכיוון שאליו נושבת הרוח. N מציין צפון, S מציין דרום, W מציין מערב ו־E מציין מזרח.

פלט

כתבו שתי שורות לפלט הסטנדרטי.

השורה הראשונה צריכה להכיל את המספר המזערי של תושבים נגועים לאחר $10^{100}$ ימים. השורה השנייה צריכה להכיל את מספר התושבים שבחירתם כנדבק הראשון משיגה את המספר המזערי של תושבים נגועים.

מגבלות

• $1\le M\le 100\,000$.
• $1\le R\le 800$.
• $1\le C\le 800$.
• $D$ היא מחרוזת באורך $M$ המכילה רק את התווים N, S, W ו־E.
• $0\le U_{i,j}\le 100\,000$ ($1\le i\le R$, $1\le j\le C$).
• קיים לפחות זוג אחד $(i,j)$ המקיים $1\le U_{i,j}$ ($1\le i\le R$, $1\le j\le C$).

תתי־משימות

1. (14 נקודות) $D$ מכילה רק W ו־E.
2. (6 נקודות) $1\le R\le 50$, $1\le C\le 50$.
3. (80 נקודות) אין מגבלות נוספות.

דוגמאות

קלט 1

6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2

פלט 1

8
8

הסבר

נבחן את המקרה שבו בוחרים בתושב $(3,1)$ כנדבק הראשון.

• עבור תושב $(2,1)$, בפרק זמן 1 ביום 1 הרוח נושבת מדרום, והתושב הסמוך מדרום כבר נגוע. לכן תושב זה יידבק החל מפרק זמן 2 ביום 1.
• עבור תושב $(3,2)$, בפרק זמן 2 ביום 1 הרוח נושבת ממערב, והתושב הסמוך ממערב כבר נגוע. לכן תושב זה יידבק החל מפרק זמן 3 ביום 1.
• עבור תושב $(1,1)$, בפרק זמן 6 ביום 1 הרוח נושבת מדרום והתושב הסמוך מדרום כבר נגוע, וגם בפרק זמן 1 ביום 2 הרוח נושבת מדרום והתושב הסמוך מדרום כבר נגוע. לכן תושב זה יידבק החל מפרק זמן 2 ביום 2.
• עבור תושב $(1,2)$, בפרק זמן 2 ביום 2 הרוח נושבת ממערב, והתושב הסמוך ממערב כבר נגוע. לכן תושב זה יידבק החל מפרק זמן 3 ביום 2.
• עבור תושב $(1,3)$, בפרק זמן 2 ביום 3 הרוח נושבת ממערב, והתושב הסמוך ממערב כבר נגוע. לכן תושב זה יידבק החל מפרק זמן 3 ביום 3.
• עבור תושב $(2,3)$, בפרק זמן 3 ביום 3 הרוח נושבת מצפון, והתושב הסמוך מצפון כבר נגוע. לכן תושב זה יידבק החל מפרק זמן 4 ביום 3.
• עבור תושב $(3,3)$, בפרק זמן 2 ביום 4 הרוח נושבת ממערב והתושב הסמוך ממערב כבר נגוע, ובפרק זמן 3 ביום 4 הרוח נושבת מצפון והתושב הסמוך מצפון כבר נגוע. לכן תושב זה יידבק החל מפרק זמן 4 ביום 4.

אף תושב נוסף לא יידבק בנגיף JOI Virus. לפיכך, כאשר בוחרים בתושב $(3,1)$ כנדבק הראשון, יהיו 8 תושבים נגועים בנגיף JOI Virus לאחר $10^{100}$ ימים.

לא משנה איזה תושב נבחר כנדבק הראשון, לא ניתן להקטין את מספר התושבים הנגועים בנגיף JOI Virus לאחר $10^{100}$ ימים אל מתחת ל־8, ולכן יש להדפיס $8$ בשורה הראשונה. אם נבחר בתושב $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,3)$, $(3,1)$, $(3,2)$ או $(3,3)$ כנדבק הראשון, יהיו 8 תושבים נגועים לאחר $10^{100}$ ימים, ולכן יש להדפיס $8$ בשורה השנייה.

קלט 2

4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4

פלט 2

3
3

הסבר

דוגמת קלט ופלט זו מקיימת את המגבלות של תת־משימה 1.