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

قواعد بازی زندگی (Game of Life) که توسط جان کانوی طراحی شده است، ساده هستند اما رفتارهای پیچیده‌ای را تولید می‌کنند. این بازی در یک شبکه‌ی دو‌بعدی انجام می‌شود که هر خانه می‌تواند دو حالت داشته باشد: زنده (1) یا مرده (0). تغییر وضعیت هر خانه براساس وضعیت همسایه‌های آن رخ می‌دهد. در ضمن در نظر داشته باشید که دو خانه را همسایه می‌گوییم اگر در یک نقطه یا یک ضلع مشترک باشند.

قواعد بازی

1. هر سلول زنده با کم‌تر از دو همسایه‌ی زنده می‌میرد (تنهایی).
2. هر سلول زنده با دو یا سه همسایه‌ی زنده، زنده می‌ماند (ثبات).
3. هر سلول زنده با بیش از سه همسایه‌ی زنده می‌میرد (ازدحام).
4. هر سلول مرده با دقیقاً سه همسایه‌ی زنده، زنده می‌شود (تولد).
5. هر سلول مرده با غیر از سه همسایه‌ی زنده، مرده می‌ماند (مرگ).

برنامه‌ای بنویسید که یک جدول $n \times n$ بگیرد، که هر خانه‌ی آن 0 ‍(مرده) یا 1 (زنده) است. این برنامه باید پس از هر مرحله، وضعیت جدید سلول‌ها را با توجه به قواعد بازی زندگی به روز کند و نتیجه را چاپ کند.

ورودی

در سطر اول ورودی، یک صحیح $n$ داده می‌شود که اندازه جدول را مشخص می‌کند. $$1 \leq n \leq 100$$

در $n$ سطر بعدی، یک جدول $n \times n$ شامل ‍0 و 1 که وضعیت اولیه‌‌ی بازی را مشخص می‌کند.

خروجی

در $n$ سطر مانند ورودی، یک جدول از 0 و 1 چاپ کنید که وضعیت جدید جدول پس از یک مرحله بازی را مشخص کند.

مثال‌ها

ورودی نمونه ۱

4
0 1 0 0
0 0 1 0
1 1 1 0
0 0 0 0

خروجی نمونه ۱

0 0 0 0
1 0 1 0
0 1 1 0
0 1 0 0

ورودی نمونه ۲

3
0 0 1
0 1 0
0 1 0

خروجی نمونه ۲

0 0 0
0 1 1
0 0 0