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

---

روی یک میز \(2n\) سکه داریم. \(n\) سکه در بالای میز با شماره‌های ۱ تا \(n\) و \(n\) سکه در پایین میز با شماره‌های ۱ تا \(n\) قرار دارند. می‌دانیم تعدادی (شاید صفر) از سکه‌ها تقلبی، و بقیه‌ی سکه‌ها اصل هستند. سکه‌های اصل با هم، و سکه‌های تقلبی باهم، هم‌وزن هستند. همچنین می‌دانیم وزن سکه‌های تقلبی کمتر از وزن سکه‌های اصلی است.

برای هر \(i\) و \(j\)، وزن سکه‌ی \(i\)ام از طرف بالا میز را با سکه‌ی \(j\)ام از طرف پایین میز مقایسه کردیم و در صورتی که:

• وزن سکه‌ی \(i\) بالا، کمتر سکه‌ی \(j\) پایین بود علامت <
• وزن سکه‌ی \(i\) بالا، بیشتر سکه‌ی \(j\) پایین بود علامت >
• وزن سکه‌ی \(i\) بالا، برابر سکه‌ی \(j\) پایین بود علامت =

را در سطر \(i\)ام ستون \(j\)ام یک جدول \(n \times n\) نوشته‌ایم.

حال می‌خواهیم از روی این جدول مشخص کنیم کدام سکه‌ها اصل و کدام سکه‌ها تقلبی هستند. ممکن است در جدول داده شده، تناقضی وجود داشته باشد و یا نتوانیم با کمک این داده‌ها وضعیت را به صورت یکتا مشخص کنیم. از شما می‌‌خواهیم برنامه‌ای بنویسید که این سه حالت را شناسایی کرده و نتیجه را اعلام کند.

برای بهتر متوجه شدن سوال، نمونه‌ها را مطالعه کنید.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت \(n\) به شما داده می‌شود. \[1 \leq n \leq 2 \,,000\]

در \(n\) سطر بعدی، در هر سطر \(n\) کاراکتر داده می‌شود که یکی از <، = یا > است. یعنی سکه‌ی \(i\)ام از \(j\)ام کوچکتر (<)، بزرگ‌تر‍ (>) یا مساوی (=) است.

خروجی

اگر اطلاعات داده شده تناقض دارند عبارت invalid، در غیراین‌صورت اگر نمی‌توانستیم به‌صورت یکتا وضعیت تقلبی یا اصل بودن را شناسایی کنیم عبارت not unique و در غیراین‌صورت در دو سطر، در هر سطر یک رشته از 0 (تقلبی) و 1 (اصل) به طول \(n\) چاپ کنید که به ترتیب وضعیت تقلبی یا اصل بودن سکه‌‌های بالای و پایین میز را نشان می‌دهد.

مثال‌ها

ورودی نمونه ۱

4
<=<<
<=<<
=>==
<=<<

خروجی نمونه ۱

0010
1011

توضیح نمونه ۱

اگر وزن ۴ سکه‌ی بالا را با \(u_1, u_2, u_3, u_4\,\) و ۴ سکه‌ی پایین را با \(d_1, d_2, d_3, d_4 \,\) نشان دهیم. داده‌های جدول بالا به صورت زیر هستند:

\[ \begin{array}{cccc} u_1 \lt d_1 & u_1 = d_2 & u_1 \lt d_3 & u_1 \lt d_4 \\ u_2 \lt d_1 & u_2 = d_2 & u_2 \lt d_3 & u_2 \lt d_4 \\ u_3 = d_1 & u_3 \gt d_2 & u_3 = d_3 & u_3 = d_4 \\ u_4 \lt d_1 & u_4 = d_2 & u_4 \lt d_3 & u_4 \lt d_4 \\ \end{array} \]

سکه‌های تقلبی با رنگ نارنجی و سکه‌های اصل با رنگ زرد در تصویر زیر مشخص شده‌اند. این تنها حالت ممکن برای تقلبی یا اصل بودن سکه‌ها است و نتیجه مقایسه‌ها هم همین را نشان می‌دهد.

ورودی نمونه ۲

3
=<<
<=<
<<=

خروجی نمونه ۲

invalid

توضیح نمونه ۲

هر دو سکه‌ی ۱ (بالا و پایین)، ۲ و ۳ باهم هم‌وزن هستند. پس می‌توانیم وزن آن‌ها را با \(w_1\)، \(w_2\) و \(w_3\) نشان دهیم.

می‌دانیم سکه‌ی ۱ (بالا) از سکه‌ی ۲ (پایین) سبک‌تر است (\(w_1 \lt w_2\)). سکه‌ی ۲ (بالا) از سکه‌ی ۱ (پایین) سبک‌تر است (\(w_2 \lt w_1\)). و این تناقض است و پاسخ invalid می‌شود.

ورودی نمونه ۳

1
=

خروجی نمونه ۳

not unique

توضیح نمونه ۳

در این حالت دو سکه داریم، سکه‌ی ۱ بالا و سکه‌ی ۱ پایین و می‌دانیم آن‌ها هم‌وزن هستند. ممکن است هر دو تقلبی و یا هر دو اصل باشند. پس نمی‌توان وضعیت آن‌ها را یکتا مشخص کرد و پاسخ not unique می‌شود.