+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- صبا یه جدول $n \times m$ داره. درون هر خونه‌ی این جدول می‌تواند حداکثر یک قارچ وجود داشته باشد. قارچ‌ها به قوانین‌ای (شبیه به [بازی زندگی](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life)) زنده می‌شوند و می‌میرند. در هر لحظه: + اگر در لحظه‌ی قبل در این خانه قارچ وجود داشته باشد و در خانه‌های مجاور آن در لحظه قبل بین ۲ تا ۳ قارچ وجود داشته باشد، زنده می‌ماند و در غیر این صورت می‌میرد. + اگر در لحظه‌ی قبل در این خانه قارج وجود نداشته باشد و در خانه‌های مجاور آن در لحظه قبل دقیقا ۳ قارچ وجود داشته باشد، یک قارچ در این خانه به وجود می‌آید. دو خانه متفاوت $(a, b)$ و $(x, y)$ را مجاور می‌نامیم اگر حداکثر یک ستون و یک سطر با هم فاصله داشته‌باشند. (فرض می‌شود که سطر اول و آخر و هم‌چنین ستون اول و آخر با هم مجاور هستند.) بنابراین هر خانه دقیقا ۸ همسایه دارد. صبا قبلا یک جدول داشت و روی آن $l$ مرحله قوانین بازی زندگی را اجرا کرد. اما از آن‌جا که جدول اولیه را فراموش کرده به شما جدول نهایی را می‌دهد و از شما می‌خواهد جدول اولیه را به او بدهید و یا بگویید که همچین جدولی وجود ندارد. # ورودی در خط اول سه عدد $n$ و $m$ و $l$ آمده‌اند در $n$ خط بعدی رشته‌ای $m$ حرفی آمده است که یعنی اگر در خط $i$ام و حرف $j$ام حرف `*` باشد در خانه‌ی $(i, j)$ یک قارچ وجود دارد و در غیر این صورت آن خانه خالی است. $$ 9 \le n \times m \le 20 $$ $$ 3 \le n, m \le 6 $$ $$ 1 \le l \le 20 $$ # خروجی در خروجی یک جدول $n \times m$ از حروف باید چاپ شود که مانند ورودی اگر در خط $i$ام حرف $j$ام `*` باشد یعنی در خانه‌ی $(i, j)$ یک قارچ وجود داشته. اگر جدول اولیه‌ای وجود نداشت پیام `impossible` چاپ شود. # مثال ## ورودی نمونه ۱ ``` 4 5 10 ....* ..*.* .*..* ..*.* ``` ## خروجی نمونه ۱ ``` ..*.* ...** **.** *.... ``` توجه کنید که جواب‌های دیگری هم ممکن است وجود داشته باشد و شما باید تنها یکی از آن‌ها را چاپ کنید. ## ورودی نمونه ۲ ``` 3 3 10 *** *** *.. ``` ## خروجی نمونه ۲ ``` impossible ```

حل سؤال در بانک سؤالات