تحقیقات اخیر بر روی سیاره‌ی «سکونیل» حاکی از وجود نوع خاصی از موجودات زنده موسوم به «ابونتو» در این سیاره است. با توجه به اطلاعات به‌دست آمده ابونتوها نیز از دو جنس نر و ماده هستند؛ نرها صورتی و ماده‌ها سبز هستند. نکته‌ی جالب توجه در مورد ابونتوها این است که آن‌ها «همبند» نیستند؛ هر یک از ابونتوها از تعدادی مولفه‌ی همبند موسوم به «پاره» تشکیل شده که همیشه در کنار هم حرکت می‌کنند و اگر از هم دور شوند باعث مرگ آن ابونتو می‌شود. یک ابونتو هنگام تولد دقیقا $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$ سطر بعدی دو عدد بنویسید که محل یکی از پاره‌هیی که باید تغییر رنگ دهد، را مشخص می‌کند؛ ابتدا ۱ یا ۲ که نشان دهید این پاره در کدام ستون است و سپس ۱ تا $n$ که نشان دهید کدام پاره از این ستون باید تغییر کند. سمت چپ‌ترین پاره‌ای که در ورودی برای هر ستون آمده، با شماره‌ی ۱ نشان داده می‌شود.

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

با انجام تغییراتی که در خروجی نمونه آمده، عکس به صورت زیر تغییر می‌یابد:

$$\underline{1} \quad 1 \quad 0 \quad 1 \quad \underline{1} \\ 1 \quad 0 \quad \underline{0} \quad 0 \quad 1$$

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