• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۶ مگابایت

کریم یک کودک ۵ ساله‌ی علاقه‌مند به نقاشی است و عشق به نقاشی باعث شده که اکثر نقاشی‌های او بسیار طویل باشند.

کریم نقاشی هایش را روی کاغذی شطرنجی می‌کشد و می‌توان آن‌ها را به صورت زیر توصیف کرد:

• هر خانه‌ی شطرنجی یا کامل سیاه است و یا کامل سفید
• از هر خانه‌ی سیاه به تمامی خانه‌های سیاه مسیر سیاه وجود دارد. مسیر سیاه یعنی دنباله‌ای از خانه‌های سیاه که هر دو خانه‌ی پشت سر هم از آن در ضلعی مشترک باشند.
• هیچ سوراخ سفیدی در شکل وجود ندارد؛ یعنی از هر خانه‌ی سفید به خارج از نقاشی مسیر سفید وجود دارد. مسیر سفید یعنی دنباله‌ای از خانه‌های سفید که هر دو خانه‌ی پشت سر هم از آن در ضلعی مشترک باشند.

کریم امروز طبق عادت هفتگی خود سراغ نقاشی رفت، اما به دلایل نامشخص فاز خستگی برداشت و تصمیم گرفت تنها دورگیری نقاشی‌اش را توصیف کند.

به خانه‌ی سیاهی در نقاشی خانه‌ی گوشه‌ای میگوییم اگر در خانه‌های مجاور راسی آن (۸ خانه) حداقل یک خانه‌ی سفید وجود داشته باشد. دورگیری‌ای که کریم توصیف می‌کند بصورت دنباله‌ای از دستورات حرکتی است که با حروف انگلیسی متناظر شده‌اند. این توصیف با حرف P شروع می‌شود و با حرف K تمام می‌شود. بقیه‌ی دنباله از حروف E، N، W و S که به ترتیب دستور حرکت به غرب، شمال، شرق و جنوب هستند تشکیل شده است. کریم در دورگیری خود از یک خانه‌ی گوشه‌ای دلخواه شروع میکند و همه‌ی خانه‌های گوشه‌ای نقاشی مدنظرش را طی می‌کند و به خانه‌ی شروع بازمیگردد. در مسیر حرکت همه‌ی خانه‌های دیده شده خانه‌های سیاه گوشه‌ای نقاشی خواهند بود. می‌دانیم که کریم دورگیری خود را به ترتیب عکس عقربه‌های ساعت انجام می‌دهد.

مادر کریم همیشه نسبت به نقاشی‌های او هم شوق وافری نشان می‌دهد؛ از این رو پس از دیدن دورگیری او، تصمیم می‌گیرد که تعداد خانه‌های سیاه این نقاشی را به دست آورد. با مقدار اندکی حافظه به او کمک کنید!

ورودی

ورودی شامل دنباله‌ی دورگیری داده شده توسط کریم است که هر حرف آن در خطی جداگانه آمده است. دنباله از حداکثر ۴۰۰۰۰۰۰ حرف تشکیل شده است. تضمین می‌شود که دنباله‌ی ورودی یک دورگیری صحیح است.

خروجی

در تنها خط خروجی شما باید تعداد خانه‌های سیاه در نقاشی توصیف شده را خروجی دهید.

مثال

ورودی نمونه ۱

P
S
S
S
E
N
E
E
S
E
E
N
N
N
N
S
S
S
W
W
N
N
W
W
W
N
S
K

خروجی نمونه ‍۱

23

نقاشی خروجی نمونه به شکل زیر است: