- محدودیت زمان: ۰.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
پویان یک نوجوان تپل است که تصمیم گرفته است با سخت کار کردن در مغازه تیله فروشی، وزن خود را کاهش دهد.
مغازه‌ی ای که پویان در آن کار میکند تیله‌ها را در $n$ اندازه مختلف عرضه میکند و هر تیله میتواند دارای پر باشد یا نباشد. پس در این مغازه میتوان $2n$ نوع تیله مختلف یافت.
مغازه‌ی پویان، $m$ مشتری ثابت دارد که هر روز به مغازه سر میزنند و به تیله‌ها نگاه میکنند. هریک از این مشتری‌ها یکسری از انواع تیله‌ها را دوست میدارد و اگر هیچیک از تیلههای موردعلاقه‌ی او در مغازه یافت نشود، او ناراحت از مغازه به بیرون میرود. همچنین هریک از این مشتری‌ها اگر تیله‌ی پردار از یک اندازه‌ای را دوست داشته باشد، هیچگاه تیله پردار از اندازه‌ی دیگری را دوست نخواهد داشت. (یعنی بین تیلههای مورد علاقه‌ی هر مشتری حداکثر یکیشان پردار است.)
پویان میخواهد از هر اندازه‌ی تیله تنها یک نوع (پردار و یا بدون پر) را انتخاب کند و تنها تولید آن را ادامه دهد، بدون اینکه هیچیک از این مشتری‌های ثابت را برنجاند. یعنی باید حداقل یک تیله مورد علاقه‌ی هریک از این مشتری‌ها در فهرست تولید وجود داشته باشد. در ضمن، پویان میخواهد که تعداد تیلههای پردار داخل فهرست تولید کمینه شود.
با ورودی گرفتن فهرست علاقه‌ی مشتریان اگر پویان میتواند با شرایط گفته شده و بدون ناراحت کردن مشتری‌هایش تولید تیله‌ها را ادامه دهد، حالتی از فهرست تولید را خروجی دهید که تعداد تیلههای پردار داخل آن‌ها کمینه است.
ورودی
در سطر اول ورودی عدد $n$ آمده است که نمایانگر تعداد اندازه‌های مختلف برای تیلههای مغازه‌ی پویان است.
در سطر دوم ورودی عدد $m$ آمده است که نمایانگر تعداد مشتری‌های ثابت مغازه‌ی پویان است.
سپس در $i$مین سطر از هریک از $m$ سطر بعدی، فهرست انواع تیله‌هایی که مشتری ثابت $i$م دوست میدارد توصیف میشود. در ابتدای سطر عدد $k_i$ آمده که برابر تعداد انواع تیله‌هاییست که این مشتری دوست میدارد. سپس $k_i$ نوع تیله بصورت دو عدد اندازه و پردار بودن توصیف شده اند. اندازه عددی طبیعی و حداکثر برابر $n$ است و پردار بودن اگر برابر ۱ بود، یعنی این مشتری تیله‌ی پردار از این اندازه را دوست میدارد و اگر برابر ۰ بود، یعنی تیله بی‌پر از این اندازه را دوست میدارد. (ممکن است مشتری از یک اندازه هم تیله‌ی پردار و هم تیله‌ی بی‌پر را دوست داشته باشد. این در دو توصیف مختلف در این سطر، گفته میشود. یکی برای تیله‌ی پردار با این اندازه و دیگری برای توصیف تیله‌ی بی‌پر با این اندازه.)
تضمین میشود هر مشتری حداکثر یک نوع تیله‌ی پردار را دوست دارد و هیچگاه یک نوع تیله دوبار در فهرست علایق یک مشتری ظاهر نمیشود.
$$1 \le n, m \le 2000$$
$$1 \le k_i \le 3000$$
$$\sum_{i = 1}^m k_i \le 3000$$
خروجی
اگر نمیتوان بدون ناراحت کردن مشتری‌های ثابت فهرست تیله‌ها را انتخاب کرد، خروجی باید تنها شامل کلمه‌ی IMPOSSIBLE شود.
اگر میتوان از هر اندازه یک نوع پردار یا بی‌پر انتخاب کرد بطوری که مشتری‌ها ناراحت نشوند، یک حالت از این انتخاب کردن‌ها را خروجی دهید که تعداد تیلههای پردارش کمینه است. تنها سطر خروجی باید شامل $n$ عدد باشد که هرکدام برابر ۰ یا ۱ است. اگر $i$مین عدد برابر ۱ بود یعنی تیله‌ی با اندازه‌ی $i$ در فهرست داده شده از این به بعد پردار تولید خواهد شد و اگر برابر ۰ بود یعنی تیله‌ی با اندازه‌ی $i$ در فهرست داده شده از این به بعد بدون پر تولید خواهد شد.
مثال
ورودی نمونه ۱
1
2
1 1 0
1 1 1
خروجی نمونه ۱
IMPOSSIBLE
ورودی نمونه ۲
5
3
1 1 1
2 1 0 2 0
1 5 0
خروجی نمونه ۲
1 0 0 0 0
ارسال پاسخ برای این سؤال