• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون نهایی سوم دوره ۲۶ المپیاد کامپیوتر

---

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

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

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

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

برای چرخاندن پادساعتگرد نیز تابع $next$ به طور مشابهی ساخته می‌شود: $$ next_{v}(u)= \begin{cases} u \oplus -1, & u \oplus -1 \ne v \ u \oplus -2, & u \oplus -1 = v \end{cases} $$

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

$$ i \oplus j = \begin{cases} i + j \mod n, & i + j \mod n \ne 0\ n, & i + j \mod n = 0 \end{cases} $$

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

ورودی

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

$$1 \le n \le 50$$

خروجی

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

زیرمسئله‌ها

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

مثال

ورودی نمونه ۱

4
0101
1000
0001
1010
0011
0001
1000
1100

خروجی نمونه ۱

10
+ 2
+ 2
- 3
+ 2
+ 4
- 1
+ 4
+ 1
- 4
- 4