+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- پس از رمزگشایی دفترچه خاطرات رستم، مشخص شد که پس از خوان هفتم و کشته شدن دیو سپید به دست رستم، رستم و سپاهش برای استراحت به سینما رفته‌اند. چینش صندلی‌های سینما به صورت یک جدول $n \times n$ است و بعضی از صندلی‌ها خراب است. رستم و سپاهش وارد سینما شدند و روی صندلی‌های سالم نشستند. تعداد صندلی‌های سالم دقیقاً به تعداد سربازان بود... در هنگام پخش فیلم، هریک از سربازان در هر زمان، نسبت به فیلم در یکی از ۳ وضعیت زیر قرار داشت: + بی‌خیال + متعجب (باخیال) + سؤال‌دار (باخیال) اگر سربازان متعجب را با علامت `!`، سربازان سؤال‌دار را با `?`، سربازان بیخیال را با `_` (underline) و صندلی‌های خراب را با `#` نمایش دهیم، یک وضعیت از سربازان در سینما می‌تواند به این صورت باشد: ????___? ##_???_? !!??#_?? !#__???? ____!!!! !!!___!! _!!!!!!# !!!????? مدت فیلم ۱۰۰۰ ثانیه بود. در طول پخش فیلم، سربازان در مورد فیلم با سربازان مجاور حرف می‌زدند و وضعیت سربازان در هر ثانیه نسبت به ثانیه قبل طبق قوانین زیر تغییر می‌کرد. + دو سرباز، مجاور محسوب می‌شوند اگر در جدول $n \times n$، صندلی‌های آن‌ها در یک ضلع یا رأس، مشترک باشند. پس هر یک از صندلی‌های میانی سینما، ٨ صندلی مجاور دارد و هریک از ۴ صندلی گوشه‌ی سینما، ٣ صندلی مجاور دارد. + اگر در میان **سربازان مجاور یک سرباز بی‌خیال**، *دقیقاً ۳ سرباز باخیال* وجود داشته باشد، در ثانیه بعد، این سرباز نیز باخیال می‌شود (اگر اکثریت ۳ سرباز مجاور متعجب بودند، او نیز متعجب می‌شود و اگر اکثریت سؤال‌دار بودند، او نیز سؤال‌دار می‌شود.) + اگر در میان **سربازان مجاور یک سرباز باخیال**، *کمتر از ۲ یا بیشتر از ۳ سرباز باخیال* وجود داشته باشد، آن سرباز در ثانیه‌ی بعد بی‌خیال می‌شود. + اگر در میان **سربازان مجاور یک سرباز متعجب**، *۲ یا ۳ سرباز باخیال* وجود داشته باشد، و در بین آن ۲ یا ۳ سرباز باخیال، تعداد سؤال‌دارها بیشتر از متعجب‌ها باشد، آن سرباز در ثانیه بعد سؤال‌دار می‌شود. + اگر در میان **سربازان مجاور یک سرباز سؤال‌دار**، *۲ یا ۳ سرباز باخیال* وجود داشته باشد، و در بین آن ۲ یا ۳ سرباز باخیال، تعداد متعجب‌ها بیشتر از سؤال‌دارها باشد، آن سرباز در ثانیه بعد متعجب می‌شود. + اگر برای یک سرباز در یک مرحله **هیچ یک از اتفاقات بالا** نیفتاد، وضعیت آن سرباز نسبت به فیلم در ثانیه بعد تغییر نمی‌کند. وضعیت سربازان را در شروع فیلم می‌دانیم. می‌خواهیم بدانیم در پایان فیلم (یعنی بعد از ۱۰۰۰ ثانیه) چه تعداد سرباز متعجب و چه تعداد سرباز سؤال‌دار هستند. # ورودی برنامه باید در ابتدا عدد $n$ را بخواند و سپس نقشه‌ی اولیه‌ی سینما را که به صورت یک جدول $n \times n$ است، بخواند. $n$ حداکثر ۵٠ خواهد بود. پس یک آرایه ۵٠ × ۵٠ برای ذخیره جدول کافی است. # خروجی در خط اول خروجی تعداد سربازان سؤال‌دار و در خط بعدی تعداد سربازان متعجب در انتهای فیلم را بنویسید. # مثال ## ورودی نمونه ۱ ``` 8 ????___? ##_???_? !!??#_?? !#__???? ____!!!! !!!___!! _!!!!!!# !!!????? ``` ## خروجی نمونه ۱ ``` 4 0 ``` -------------- ## ورودی نمونه ۲ ``` 30 ??_???_?_?_?_#?_????_?____??__ _?__?_???_?_?#???__?_??_?_???? __???___???__#________________ ________???__##!!!!!____?_____ ________???__#________________ _____________#________________ _____________??_______________ ______________________________ ______________________________ ______!!!!!____________??????_ ______________________________ ___________!?!?!?!?!!!________ _____######____#########______ ________#_??????!!!!??________ ________#_____________________ ________#___________?!?!?!?!__ ______________________________ _____________________________? ____________________________?? ____!!!_______________#######? ____________________________?? _____________________________? ______________________________ ____________________!!_!!_____ ______________________________ ______________!_______________ ####_______#!!!!!_____________ #__!_!!!_!!!!!!!!!!!!_!!!_!___ #_!!!!!!!!!!!!!!!!!!!!!!!!!!__ #############!!!!!!!!!!!!!!!!_ ``` ## خروجی نمونه ۲ ``` 9 19 ``` -------------- ## مثالی از وضعیت سربازان در ۱۰۰۰ مرحله در شروع فیلم: ``` ????___? ##_???_? !!??#_?? !#__???? ____!!!! !!!___!! _!!!!!!# !!!????? ``` ثانیه ۱: ``` _???__?_ ##___?_? !!?_#___ !#?_____ !__!?___ !_______ _______# !______? ``` ثانیه ۲: ``` __?___?_ ##_?__?_ !_?_#___ !#!_____ !__?____ ________ _______# ________ ``` ثانیه ۳: ``` ________ ##??____ __??#___ !#??____ _!______ ________ _______# ________ ``` ثانیه ۴: ``` ________ ##??____ ____#___ _#_?____ _!?_____ ________ _______# ________ ``` ثانیه ۵: ``` ________ ##______ __??#___ _#?_____ __?_____ ________ _______# ________ ``` ثانیه ۶: ``` ________ ##______ __??#___ _#?_____ ________ ________ _______# ________ ``` در ثانیه ۷ تا ۱۰۰۰ (تا پایان فیلم) وضعیت سربازان به این شکل ثابت است: ``` ________ ##______ __??#___ _#??____ ________ ________ _______# ________ ```