+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روی یک میز $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 ```` <details> <summary> **توضیح نمونه ۱** </summary> اگر وزن ۴ سکه‌ی بالا را با $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} \] سکه‌های تقلبی با رنگ نارنجی و سکه‌های اصل با رنگ زرد در تصویر زیر مشخص شده‌اند. این تنها حالت ممکن برای تقلبی یا اصل بودن سکه‌ها است و نتیجه مقایسه‌ها هم همین را نشان می‌دهد.  </details> ## ورودی نمونه ۲ ``` 3 =<< <=< <<= ```` ## خروجی نمونه ۲ ``` invalid ```` <details> <summary> **توضیح نمونه ۲** </summary> هر دو سکه‌ی ۱ (بالا و پایین)، ۲ و ۳ باهم هم‌وزن هستند. پس می‌توانیم وزن آن‌ها را با $w_1$، $w_2$ و $w_3$ نشان دهیم. می‌دانیم سکه‌ی ۱ (بالا) از سکه‌ی ۲ (پایین) سبک‌تر است ($w_1 \lt w_2$). سکه‌ی ۲ (بالا) از سکه‌ی ۱ (پایین) سبک‌تر است ($w_2 \lt w_1$). و این تناقض است و پاسخ `invalid` می‌شود. </details> ## ورودی نمونه ۳ ``` 1 = ```` ## خروجی نمونه ۳ ``` not unique ```` <details> <summary> **توضیح نمونه ۳** </summary> در این حالت دو سکه داریم، سکه‌ی ۱ بالا و سکه‌ی ۱ پایین و می‌دانیم آن‌ها هم‌وزن هستند. ممکن است هر دو تقلبی و یا هر دو اصل باشند. پس نمی‌توان وضعیت آن‌ها را یکتا مشخص کرد و پاسخ `not unique` می‌شود. </details>

حل سؤال در بانک سؤالات