دو گراف $n$ راسی به شما داده شده است که راس‌های آن‌ها از $1$ تا $n$ شماره‌گذاری شده اند. در هر مرحله می‌توان یال‌های متصل به یک راس در گراف اول را یک بار به صورت ساعتگرد یا پادساعتگرد چرخاند.

عمل چرخاندن یک راس مانند $v$ به این شکل انجام می‌شود که در ازای هر یال از $v$ به $u$ در گراف، یک یال جدید از $v$ به $next_v(u)$ قرار داده می‌شود و تمامی یال‌های قدیمی راس $v$ پاک می‌شود.

برای حرکت چرخاندن ساعتگرد، تابع $next$ به شکل زیر تعریف می‌شود:

\begin{equation*} next_{v}(u)= \begin{cases} u \oplus 1, & u \oplus 1 \ne v \\ u \oplus 2, & u \oplus 1 = v\\ \end{cases} \end{equation*}

برای چرخاندن پادساعتگرد نیز تابع $next$ به طور مشابهی ساخته می‌شود:

\begin{equation*} next_{v}(u)= \begin{cases} u \oplus -1, & u \oplus -1 \ne v \\ u \oplus -2, & u \oplus -1 = v\\ \end{cases} \end{equation*}

منظور از عملگر $\oplus$ جمع دوری است که به شکل زیر تعریف می شود:

\begin{equation*} i \oplus j = \begin{cases} i + j \mod n, & i + j \not\equiv 0 \mod n\\ n, & i + j \equiv 0 \mod n \\ \end{cases} \end{equation*}

هدف تبدیل گراف اول به گراف دوم در تعدادی حرکت است. آیا این کار امکان پذیر است؟

در خط اول ورودی عدد طبیعی $n$، تعداد راس‌های گراف‌ها آمده است.

در $n$ خط بعدی از ورودی در هر خط یک رشته‌ی $n$ حرفی از 0 و 1 آمده است که ماتریس مجاورت گراف اول را نشان می‌دهد و 1 بودن حرف $j$ام خط $i$ام وجود یک یال از $i$ به $j$ در گراف اول را نشان می‌دهد.

در $n$ خط بعدی به حالت مشابه ماتریس مجاورت گراف دوم آمده است.

در صورتی که نمی‌توان گراف اول را به گراف دوم تبدیل کرد در یک خط عبارت impossible را چاپ کنید.

در غیر این‌صورت ابتدا تعداد حرکات لازم برای تبدیل گراف اول به گراف دوم را چاپ کنید و در خطوط بعدی حرکات را به شکل - v یا + v چاپ کنید. - v یک چرخاندن ساعتگرد بر روی راس $v$ و + v یک چرخاندن پادساعتگرد بر روی راس $v$ را نشان می‌دهد. دقت کنید لزومی ندارد که تعداد حرکات مینیمم باشد و جواب شما اگر کمتر از $300000$ حرکت داشته باشد قابل قبول است.

• زیرمسئله اول (۱۱ نمره): $n \le 7$
• زیرمسئله دوم (۱۱ نمره): تضمین می‌شود درجه هر راس در گراف‌ها دقیقاً یک است.
• زیرمسئله سوم (۲۲ نمره): تضمین می‌شود گراف‌ها درخت هستند.
• زیرمسئله چهارم(۵۶ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le n \le 50$
• تضمین می‌شود ماتریس‌های ورودی متقارن هستند و درایه‌های روی قطرشان برابر با صفر است.

• سوال بعد