- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
برای ضیافت دانشگاه امیرکبیر به مناسبت آغاز سریع ترم جدید تعداد $N$ لامپ کم‌مصرف دوستدار طبیعت تهیه کرده‌ایم که با شماره‌های یک تا $N$ شماره‌گذاری شده‌اند. لامپ‌ها را به کلیدهای زیر متصل کرده‌ایم:
- کلید ۱: وقتی این کلید زده شود تمامی لامپ ها تغییر وضعیت می‌دهند و اگر خاموش هستند روشن می‌شوند و اگر روشن باشند خاموش می‌شوند.
- کلید ۲: تمامی لامپ‌ها با شماره فرد تغییر وضعیت می‌دهند.
- کلید ۳: تمامی لامپ‌ها با شماره زوج تغییر وضعیت می‌دهند.
- کلید ۴: تمامی لامپ‌های با شماره $3k+1$ تغییر وضعیت می‌دهند مانند ۱، ۴، ۷، ...
از طرفی برای کنترل استهلاک ضیافت، یک شمارنده در دفتر دانشگاه وجود دارد که تعداد کل فشردن کلیدها را کنترل می‌کند. هنگامی که ضیافت آغاز می‌شود کل لامپ‌ها روشن هستند و عدد شمارنده برابر با صفر است.
در طول ضیافت کلیدها به ترتیبی فشرده شده‌اند و عدد شمارنده به $C$ افزایش یافته است. وضعیت نهایی تعدادی از لامپ‌ها را می‌دانیم. می‌خواهیم بدانیم سایر لامپ‌ها چه وضعیت‌هایی ممکن است داشته باشند.
اعداد $N$ و $C$ و وضعیت نهایی برخی از لامپ‌ها داده می‌شود. برنامه‌ای بنویسید که تمامی حالات نهایی ممکن با $C$ بار فشردن کلیدها و وضعیت نهایی داده شده را مشخص کند. حالات نهایی حساب شده نباید تکراری باشند.
ورودی
- خط اول: عدد $N$ که تعداد لامپ هاست.
- خط دوم: عدد $C$ که تعدادن فشردن کلیه کلیدهاست. ($1 \leq C \leq 10000$)
- خط سوم: لامپ‌هایی که باید در آخر روشن باشند که در آخر خط به منظور نشان دادن پایان ورودی $-1$ می‌آید.
- خط چهارم: لامپ‌هایی که باید در آخر خاموش باشند که در آخر خط به منظور نشان دادن پابان ورودی $-1$ می‌آید.
خروجی
شامل تمامی حالات نهایی ممکن با ویژگی‌های ورودی است. هر خط شامل $N$ کاراکتر است که وضعیت لامپ‌ها را در آن حالت بیان می‌کند. اگر لامپی خاموش باشد عدد $0$ و اگر روشن باشد عدد $1$ را می‌گذاریم.
اگر هیچ حالتی وجود نداشت باید در خروجی عبارت IMPOSSIBLE چاپ شود.
مثال
ورودی نمونه
10
1
-1
7 -1
خروجی نمونه
0000000000
0101010101
0110110110
ارسال پاسخ برای این سؤال