هل تعرف شركة Just Odd Inventions Co., Ltd.؟ يتمثل عمل هذه الشركة في صنع «اختراعات غريبة فحسب». سنسميها هنا JOI Company.

طورت JOI Company فيروسًا جديدًا يسمى «JOI Virus». وتريد إجراء تجربة بإصابة سكان IOI Island بهذا الفيروس.

تأخذ IOI Island شكل مستطيل. توجد فيها $R-1$ طرق متوازية تمتد من الشرق إلى الغرب، و$C-1$ طرق متوازية تمتد من الشمال إلى الجنوب، فتقسم الجزيرة إلى $RC$ مناطق. يسكن كل منطقة شخص واحد فقط. نسمي الشخص الذي يسكن المنطقة رقم $i$ من الشمال ورقم $j$ من الغرب ($1 \le i \le R$، $1 \le j \le C$) «الساكن $(i,j)$».

يوجد في كل يوم في IOI Island عدد من الفترات الزمنية يساوي $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}{l} M\quad R\quad C \\ D \\ U_{1,1}\quad\cdots\quad U_{1,C} \\ \vdots\qquad\qquad\vdots \\ U_{R,1}\quad\cdots\quad U_{R,C} \end{array} $$

$D$ سلسلة طولها $M$ تمثل الاتجاه الذي تأتي منه الرياح في IOI Island. تتكون $D$ من أربعة أنواع من المحارف: 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)$ ليكون أول مصاب، فسيكون عدد المصابين بعد $10^{100}$ يوم هو $8$، لذلك يجب إخراج $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.