+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی نتوانست ترب را پیدا کند و خیلی از لحاظ روانی به هم ریخته... تصمیم گرفت یک زمین کشاورزی بخرد و در آن ترب بکارد...* زمینی که علی خریده است یک مستطیل $n \times m$ است. این زمین دارای $nm$ قطعه است. قطعات این زمین به صورت یک جدول با $n$ سطر و $m$ستون است. در هر قطعه از این زمین می‌توان یک ترب کاشت یا آن را خالی گذاشت. علی می‌خواهد دقیقاً در $s$ قطعه از این زمین ترب بکارد. علی دچار وسواس تقارن شده و می‌خواهد این کار را طوری انجام دهد، که جدول زمین کشاورزی متقارن باشد. یعنی حداقل یکی از دو محور تقارن افقی یا عمودی وجود داشته باشد که زمین کشاورزی نسبت به آن متقارن باشد. به علی کمک کنید تا روشی برای کاشت $s$ ترب در زمین پیدا کند و اگر این کار ممکن نیست این خبر بد را به او اطلاع دهید. # ورودی در تنها سطر ورودی سه عدد صحیح $n$ و $m$ و $s$ با فاصله از هم آمده است که نشان دهنده ابعاد زمین علی و تعداد قطعاتی است که می‌خواهد در آن‌ها ترب بکارد. $$1 \le n, m \le 100$$ $$0 \le s \le nm $$ # خروجی در خط اول خروجی در صورت امکان پذیر بودن این کار کلمه `possible` و در صورت ممکن نبودن کلمه `impossible` را چاپ کنید. در صورت امکان پذیر بودن باید در $n$ سطر بعدی و در هر سطر یک رشته از $m$ کاراکتر بدون فاصله چاپ شود.اگر در قطعه سطر $i$ام ستون $j$ام ترب کاشته شود کاراکتر `T` و در صورت خالی بودن آن کاراکتر `E` را چاپ کنید. توجه کنید که در صورت وجود جواب، می‌توانید هر جواب دلخواهی را چاپ کنید و مساله جواب یکتا ندارد. # مثال ## ورودی نمونه ۱ ``` 3 3 5 ``` ## خروجی نمونه ۱ ``` possible TTT ETE ETE ``` با کاشت ترب‌ها به روش فوق زمین کشاورزی نسبت به محور عمودی متقارن خواهد بود. ## ورودی نمونه ۲ ``` 4 4 1 ``` ## خروجی نمونه ۲ ``` impossible ``` هیچ روشی برای کاشتن ترب در زمین کشاورزی وجود ندارد. ## ورودی نمونه ۳ ``` 2 3 1 ``` ## خروجی نمونه ۳ ``` possible EEE ETE ``` با کاشت ترب‌ها به روش فوق زمین کشاورزی نسبت به محور عمودی متقارن خواهد بود. ## ورودی نمونه ۴ ``` 2 2 2 ``` ## خروجی نمونه ۴ ``` possible TE TE ``` با کاشتن ترب‌ها به روش فوق زمین کشاورزی نسبت به محور افقی متقارن خواهد بود. # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary> راهنمایی ۱ </summary> با کمی بررسی متوجه می‌شویم که اگر حداقل یکی از $n$ و $m$ فرد باشند، علی همواره می‌تواند روشی برای کاشت ترب در زمین پیدا کند. حال اگر هر دو بعد مستطیل زوج باشند، در می‌یابیم که تعداد ترب‌های کاشته شده هم باید زوج باشد وگرنه زمین ما نمی‌تواند نسبت به هیچ یک از محورهای تقارن قرینه باشد. دلیل آن هم این است که محورهای تقارن ما در یک طرف خود زوج و در طرف دیگر فرد ترب کاشته شده دارند که شرط تقارن را نقض می‌کند. </details> <details class="blue"> <summary>راهنمایی ۲</summary> اگر $n$ و $m$ زوج باشند، می‌دانیم که حتما $s$ هم باید زوج باشد تا بتوانیم جدول مورد نظر را بسازیم. در این صورت می‌توانیم سطرها را به دو نیمه بالا و پایین تقسیم کنیم و به هر قسمت، نیمی از ترب‌ها را اختصاص دهیم. برای متقارن بودن جدول هم به این صورت عمل می‌کنیم که در نیمه بالا سطرها را از پایین به بالا و در نیمه پایین سطرها را از بالا به پایین کار می‌کنیم. همچنین در حین حرکت روی هر سطر نیز خانه‌های آن را از سمت به چپ به راست پر می‌کنیم. </details> <details class="blue"> <summary>راهنمایی ۳</summary> حال به بررسی حالاتی می‌پردازیم که حداقل یکی از $n$ و $m$ فرد است. فرض کنیم $n$ فرد است (اگر نبود، همه این کارها را به صورت ستونی انجام دهید). در ابتدا سطر وسط را در نظر می‌گیریم و شروع به پر کردن آن می‌کنیم. اگر ترب‌ها در سطر وسط جا می‌شدند که همه را همان‌جا می‌گذاریم. در غیر این صورت،‌ بیشترین تعداد ترب را در آن‌جا می‌گذاریم به‌طوری که تعداد ترب‌های باقی‌مانده زوج باشد (این تعداد بسته به زوجیت $s$ تعیین می‌شود و برابر $m$ یا $m - 1$ است). حال بدون در نظر گرفتن سطر وسط، نیمه بالای سطرهای جدول و نیمه پایین آن را با ترب‌های باقی‌مانده پر می‌کنیم به صورتی که نصف ترب‌ها به نیمه پایین و نصف دیگر به نیمه بالا برسد و این‌کار را همانند روش گفته شده در پایان راهنمایی قبل انجام می‌دهیم. با این الگوریتم، جدول نسبت به محور افقی متقارن خواهد شد. </details>

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