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

---

روی یک میز $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 می‌شود.