تحقیقات اخیر بر روی سیاره‌ی سکونیل حاکی از وجود نوع خاصی از موجودات زنده موسوم به ابونتو در این سیاره است. با توجه به اطلاعات به‌دست آمده ابونتوها نیز از دو جنس نر و ماده هستند؛ نرها صورتی و ماده‌ها سبز هستند. نکته‌ی جالب توجه در مورد ابونتوها این است که آن‌ها همبند نیستند؛ هر یک از ابونتوها از تعدادی مؤلفه‌ی همبند موسوم به پاره تشکیل شده‌اند که همیشه در کنار هم حرکت می‌کنند و اگر ازهم دور شوند باعث مرگ آن ابونتو می‌شود. یک ابونتو هنگام تولد دقیقا ‎$k$‎ پاره است که به مرور زمان بزرگ‌تر شده و پاره‌های جدیدی پیدا می کند.

ابونتوها هنگام ورزش‌صبحگاهی در دو ستون، کنار هم می‌ایستند و ورزش می‌کنند. این ستون‌ها ازپاره‌های سبز (مربوط به ماده‌ها) و صورتی (مربوط به نرها) تشکیل شده است. هر کدام از ستون‌ها دقیقا شامل ‎$n$‎ پاره است. پاره‌های یک ابونتو می‌توانند در هر دوستون وجود داشته باشند. یک پاره از یک ابونتو که در ‎$i$‎امین مکان یک ستون ایستاده با پاره‌ی ‎$i-1$‎ام و ‎$i+1$‎ام از همان ستون و هم‌چنین پاره‌ی ‎$i$‎ام از ستون دیگر همسایه به حساب می‌آید. با توجه به همسایگی گفته شده می‌دانیم پاره‌های یک ابونتوی در حال ورزش‌صبحگاهی تشکیل یک شکل همبند می‌دهند.

عکسی توسط یک تلسکوپ بسیار قوی از ابونتوها درحال ورزش‌صبحگاهی گرفته شده است. ولی در عکسی که به‌دست ما رسیده به دلیل مشکلات عکس برداری، رنگ تعدادی از پاره‌ها اشتباه افتاده است (سبز به جای صورتی یا صورتی به جای سبز). با توجه به اینکه می‌دانیم در عکس گرفته شده همه‌ی ابونتوها زنده هستند و هم‌چنین می‌دانیم که هر ابونتو حداقل از ‎$k$‎ پاره تشکیل شده است، یک عکس می‌تواند نامعتبر باشد. می‌خواهیم شبیه‌ترین عکس (عکس با کم‌ترین تعداد تغییر) به عکس فعلی را پیدا کنیم که معتبر باشد. دقت کنید که اگر دو ابونتوی صورتی ‎(یا سبز)‎ کنار هم ایستاده باشند، قادر به تشخیص پاره‌های آن‌ها از هم نیستیم و حتی نمی‌توانیم تشخیص دهیم که این یک ابونتو است یا دو ابونتو.

‎ برنامه‌ای بنویسید که:

• $n$‎ و ‎$k$‎ و اطلاعات عکس را از ورودی بخواند؛
• مشخص کند که عکس گرفته شده با شبیه‌ترین عکس معتبر چند تفاوت دارد؛ و
• تعداد تفاوت‌ها و شبیه‌ترین عکس معتبر (اگر چند جواب وجود دارد یکی از آن‌ها را به دل‌خواه) را در خروجی بنویسید.

می‌توانید فرض کنید که ورودی‌های داده شده به برنامه‌ی شما حتما دارای جواب هستند.‎

• سطر نخست ورودی به ترتیب شامل ‎$n$‎ و ‎$k$‎ است ‎$(1 \leq n \leq 1000)$‎ و ‎$(1 \leq k \leq 100)$‎.
• سطر دوم و سوم هر کدام شامل ‎$n$‎ عدد هستند که با یک فاصله از هم جدا شده‌اند و به ترتیب نشان دهنده‌ی رنگ پاره‌های ستون اول و دوم عکس هستند؛ در این سطرها صفر نشان دهنده‌ی رنگ صورتی و یک نشان دهنده‌ی رنگ سبز می‌باشد.

• در سطر اول خروجی تعداد تفاوت‌های عکس اولیه با شبیه‌ترین عکس معتبر به آن را بنویسید؛ این عدد را با ‎$m$‎ نشان می‌دهیم.
• در هر یک از ‎$m$‎ سطر بعدی دو عدد بنویسید که محل یکی از پاره‌هایی که باید تغییر رنگ دهد، را مشخص می‌کند؛ ابتدا ‎$1$‎ یا ‎$2$‎ که نشان دهید این پاره در کدام ستون است و سپس ‎$1$‎ تا ‎$n$‎ که نشان دهید کدام پاره از این ستون باید تغییر کند. سمت چپ‌ترین پاره‌ای که در ورودی برای هر ستون آمده، با شماره‌ی ‎$1$‎ نشان داده می‌شود.‎

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

• سوال بعد
• سوال قبل