فلاپی‌برد بی‌کیفیت


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

احتمالاً بازی Flappy Bird را دیده‌اید. در این بازی، یک پرنده از سمت چپ به راست حرکت می‌کند. مانع‌ها در این بازی یا بخشی از بالا یا پایین صفحه را مسدود کرده‌اند و هدف این است که پرنده بدون برخورد به موانع به انتهای بازی برسد.

توضیح تصویر

در نسخه‌ی ساده‌شده‌ی این بازی، فرض کنید کل محیط بازی به‌صورت یک جدول 2×n2 \times n است. هر خانه از جدول می‌تواند یکی از سه وضعیت زیر را داشته باشد:

  • در آن خانه پرنده قرار دارد (دقیقاً یک خانه شامل پرنده است).
  • در آن خانه مانع وجود دارد.
  • آن خانه خالی است.

در ابتدا، می‌دانیم که پرنده در خانه‌ی بالا-چپ قرار دارد و قصد دارد به خانه‌ی پایین-راست برود (تضمین می‌شود که این دو خانه هیچگاه مانع ندارند). پرنده می‌تواند در هر حرکت به خانه‌های مجاور ضلعی (در صورت نبود مانع) حرکت کند. سوال این است که آیا پرنده می‌تواند مسیری برای رسیدن به مقصد پیدا کند یا نه؟

برای درک بهتر سوال، به نمونه‌ها مراجعه کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت nn داده می‌شود که تعداد ستون‌های جدول را نشان می‌دهد.

1n1001 \leq n \leq 100

در دو سطر بعدی، هر سطر شامل nn کاراکتر است که کاراکتر سطر iiام و ستون jjام وضعیت خانه‌ی متناظر در جدول را مشخص می‌کند. کاراکتر X نشان‌دهنده‌ی مانع و کاراکتر O نشان‌دهنده‌ی باز بودن خانه است.

خانه‌ی سطر اول از ستون اول و خانه‌ی سطر دوم از ستون nnام مبدا و مقصد پرنده هستند و همیشه با O مشخص می‌شوند.

خروجی🔗

در تنها سطر خروجی، در صورت وجود مسیر، رشته‌ی Hooraaay!:)) و در غیر این صورت رشته‌ی Awww:(( را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

8
OOXOOOXX
XOOOXOOO
Plain text

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

Hooraaay!:))
Plain text

توضیح تصویر

ورودی نمونه ۲🔗

5
OOOXO
OXXOO
Plain text

خروجی نمونه ۲🔗

Awww:((
Plain text

توضیح تصویر