+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** _چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن‌ها در طی جهان‌گردی‌شان با مسائلی روبه‌رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید._ ![](http://s9.picofile.com/file/8280858484/bug_PNG3980.png) آن‌ها پس از این که از شر ماموران سیا رها شدند، در آلمان نیز دچار مشکل دیگری شدند. هنگامی که چرزه در کوچه پس کوچه‌های برلین قدم می‌زد یک تکه کاغذ روی زمین پیدا کرد که از او خواسته بود تا یک الگوریتم برای مرتبسازی تعدادی اعداد به صورت **غیرنزولی** بنویسد ولی با این که چرزه این همه ادعا داشت، نتوانست یک الگوریتم خوب پیدا بکند و این الگوریتم را نوشت: ```C++ for i = 1 to n do { t = 0; for j = 1 to n do if(a[j] < a[i]) t = t + 1; ans[t+1] = a[i]; } ``` در این الگوریتم طول دنباله $n$ است و خانه‌های آن از ۱ تا $n$ شماره‌گذاری شده‌اند. آرایه‌ی $ans$ نیز آرایه‌ی خروجی است. ** توجه کنید که تمام مقادیر دنباله‌ی $ans$ در ابتدا ۰ هستند!** پشمک هنگامی که این الگوریتم را دید، وجود باگ را در برنامه حس کرد! ولی از آن جایی که چرزه آدم بسیار مغروری بود، باگ‌دار بودن الگوریتمش را نپذیرفت. بنابراین پشمک باید به او ثابت کند که الگوریتمش باگ‌دار است. هم چنین پشمک خیلی هم تنبل است بنابراین می‌خواهد که هم مشقش را انجام دهد و هم چرزه را ضایع کند! بنابراین پشمک باید یک دنباله از اعداد طبیعی مانند $a$ بگیرد که برخی از خانه‌های آن پر نشده است. او باید جوری تمام این خانه‌ها را با **اعداد طبیعی** پر کند که الگوریتم چرزه آن را به درستی مرتب‌سازی نکند. از بین تمام روش‌های ممکن برای پر کردن این دنباله، پشمک باید به طرزی این خانه‌ها را پر کند که $Mex$ دنباله‌ی نهایی بیشینه شود. توجه کنید که در یک دنباله، $Mex$ آن دنباله را به صورت **کوچک ترین عدد طبیعی** که در دنباله آورده نشده باشد، تعریف می‌کنیم. برای مثال $Mex$ دنباله‌ی $\left [ 4, 3, 1\right ]$ برابر با $2$ می باشد. # ورودی در خط اول یک عدد $n$ می آید که طول دنباله‌ی ناکامل است. در خط بعد $n$ عدد آورده می‌شود که یا $-1$ است به این معنا که آن خانه پر نشده است و یا یک عدد طبیعی است که به معنای مقدار آن خانه در دنباله است. **تضمین می‌شود که حداقل یک خانه وجود دارد که مقدار نداشته باشد.** $$1 \leq n \leq 30\ 000$$ $$1 \leq a_i \leq 10^{9}$$ # خروجی **اگر امکان پر کردن دنباله به صورتی که الگوریتم چرزه برای آن اشتباه، جواب بدهد، وجود نداشته باشد، عبارت `impossible` را چاپ کنید**. در غیر این صورت، در یک خط پر‌شده‌ی دنباله‌ی ورودی را به صورتی که الگوریتم چرزه آن را اشتباه مرتب سازی کند و $Mex$ آن بیشینه‌ی ممکن باشد، چاپ‌ کنید. **از آن جایی که ممکن است چند جواب برای یک ورودی وجود داشته باشد، یکی از آن‌ها را به دلخواه چاپ کنید.** # مثال ## ورودی نمونه ۱ ``` 4 1 -1 3 4 ``` ## خروجی نمونه ۱ ``` 1 4 3 4 ``` ## ورودی نمونه ۲ ``` 4 12 -1 -1 -1 ``` ## خروجی نمونه ۲ ``` 12 12 1 2 ```

مسئله‌ی خاص

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

چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن‌ها در طی جهان‌گردی‌شان با مسائلی روبه‌رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید.

آن‌ها پس از این که از شر ماموران سیا رها شدند، در آلمان نیز دچار مشکل دیگری شدند.

هنگامی که چرزه در کوچه پس کوچه‌های برلین قدم می‌زد یک تکه کاغذ روی زمین پیدا کرد که از او خواسته بود تا یک الگوریتم برای مرتبسازی تعدادی اعداد به صورت غیرنزولی بنویسد ولی با این که چرزه این همه ادعا داشت، نتوانست یک الگوریتم خوب پیدا بکند و این الگوریتم را نوشت:

for i = 1 to n do
{ 
  t = 0;
  for j = 1 to n do
    if(a[j] < a[i]) t = t + 1;
  ans[t+1] = a[i];
}

در این الگوریتم طول دنباله $n$ است و خانه‌های آن از ۱ تا $n$ شماره‌گذاری شده‌اند. آرایه‌ی $ans$ نیز آرایه‌ی خروجی است. ** توجه کنید که تمام مقادیر دنباله‌ی $ans$ در ابتدا ۰ هستند!**

پشمک هنگامی که این الگوریتم را دید، وجود باگ را در برنامه حس کرد! ولی از آن جایی که چرزه آدم بسیار مغروری بود، باگ‌دار بودن الگوریتمش را نپذیرفت. بنابراین پشمک باید به او ثابت کند که الگوریتمش باگ‌دار است. هم چنین پشمک خیلی هم تنبل است بنابراین می‌خواهد که هم مشقش را انجام دهد و هم چرزه را ضایع کند!

بنابراین پشمک باید یک دنباله از اعداد طبیعی مانند $a$ بگیرد که برخی از خانه‌های آن پر نشده است. او باید جوری تمام این خانه‌ها را با اعداد طبیعی پر کند که الگوریتم چرزه آن را به درستی مرتب‌سازی نکند. از بین تمام روش‌های ممکن برای پر کردن این دنباله، پشمک باید به طرزی این خانه‌ها را پر کند که $Mex$ دنباله‌ی نهایی بیشینه شود.

توجه کنید که در یک دنباله، $Mex$ آن دنباله را به صورت کوچک ترین عدد طبیعی که در دنباله آورده نشده باشد، تعریف می‌کنیم. برای مثال $Mex$ دنباله‌ی $\left [ 4, 3, 1\right ]$ برابر با $2$ می باشد.

ورودی🔗

در خط اول یک عدد $n$ می آید که طول دنباله‌ی ناکامل است.

در خط بعد $n$ عدد آورده می‌شود که یا $-1$ است به این معنا که آن خانه پر نشده است و یا یک عدد طبیعی است که به معنای مقدار آن خانه در دنباله است.

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

$1 \leq n \leq 30\ 000$ $1 \leq a_i \leq 10^{9}$

خروجی🔗

اگر امکان پر کردن دنباله به صورتی که الگوریتم چرزه برای آن اشتباه، جواب بدهد، وجود نداشته باشد، عبارت impossible را چاپ کنید. در غیر این صورت، در یک خط پر‌شده‌ی دنباله‌ی ورودی را به صورتی که الگوریتم چرزه آن را اشتباه مرتب سازی کند و $Mex$ آن بیشینه‌ی ممکن باشد، چاپ‌ کنید.

از آن جایی که ممکن است چند جواب برای یک ورودی وجود داشته باشد، یکی از آن‌ها را به دلخواه چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

4
1 -1 3 4

خروجی نمونه ۱🔗

1 4 3 4

ورودی نمونه ۲🔗

4
12 -1 -1 -1

خروجی نمونه ۲🔗

12 12 1 2

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** _چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن‌ها در طی جهان‌گردی‌شان با مسائلی روبه‌رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید._ ![](http://s9.picofile.com/file/8280961700/unnamed.jpg) اکنون آن‌ها به دلیلی (!) وارد کازان روسیه شده‌اند و می‌خواهند برای مدتی در آن جا اتراق کنند. آن‌ها هنگام ورود به کازان، از آن جایی که سه مشکل مرگبار را گذرانده‌اند، بسیار خسته شده‌اند و سعی می‌کنند بازی حدسی بکنند اما در این هنگام دوباره مشکلی پیش می‌آید و آن این است که پشمک بازی حدسی را دوست ندارد و ممکن است به این دلیل بین او و چرزه تفرقه بیفتد و ... در این بازی، چرزه یک عدد مانند $x$ انتخاب می‌کند که عضو $\left [ 1, n \right ]$ است ولی به پشمک نمی‌گوید! پشمک می تواند تعدادی عدد **در بازه‌ی $\left[1, n \right]$ **روی کاغذ بنویسد و در نهایت به چرزه بدهد. چرزه نیز پس از تحویل گرفتن کاغذ، تک تک روی تمام اعداد کاغذ دست می‌گذارد و ب.م.م $x$ و آن عدد روی کاغذ را به پشمک می‌گوید. (چرزه هیچ وقت دروغ نمی‌گوید.) سپس پشمک باید عدد را با توجه به اطلاعات داده شده پیدا کند. پشمک که اصلا از این بازی خوشش نیامده است، از شما می‌خواهد تا برنامه‌ای برای او بنویسید تا با گرفتن عدد $n$ حداقل تعداد عدد مورد نیاز برای نوشتن روی کاغذ و هم چنین این اعداد را به او بگویید. (وگرنه سفرشان همین جا پایان می‌یابد!) **تنها نکته‌ای که باید توجه کنید، این است که پشمک ابتدا تمام اعداد را می‌نویسد سپس چرزه جواب آن‌ها را می‌دهد.** # ورودی در یک خط یک عدد $n$ داده می‌شود که بدین معنا است که $1 \leq x \leq n$. $$1\leq n \leq 100\ 000$$ # خروجی در خط اول خروجی یک عدد $t$، که حداقل تعداد اعداد ممکن برای نوشتن روی کاغذ، برای آگاهی یافتن از عدد $x$ است، نمایش داده شود. در خط دوم نیز $t$ عدد که اعداد مورد نیاز برای پرسش هستند را **به ترتیب صعودی** چاپ کنید. **هم چنین توجه کنید که هر عدد خروجی باید خودش در بازه‌ی $\left [1, n \right]$ باشد.** # مثال ## ورودی نمونه ۱ ``` 6 ``` ## خروجی نمونه ۱ ``` 3 3 4 5 ``` ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` 1 2 ``` ## توضیح: در مثال اول با امتحان کردن، می‌توان دید که پرسیدن دو عدد برای آگاهی یافتن از عدد $x$ کافی نیست؛ برای مثال اگر فقط دو عدد $\langle 3, 4\rangle $ را بنویسیم، نمی‌توانیم عدد $5$ را از عدد $1$ تشخیص بدهیم. برای اعداد $1$، $2$، $3$، $4$، $5$ و $6$ پاسخ‌های چرزه به $\langle 3, 4, 5 \rangle $ به ترتیب برابر با $\langle 1, 1, 1 \rangle$ ، $\langle 1, 2, 1 \rangle$ ، $\langle 3, 1, 1 \rangle$ ، $\langle 1, 4, 1 \rangle$ ، $\langle 1, 1, 5 \rangle$ و $\langle 3, 2, 1 \rangle$ است که همان طور که می‌بینید، پاسخ‌ها برای هیچ دو عددی در بازه‌ی $1$ تا $6$ یکسان نیست.

مسئله‌ی حدسی

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

اکنون آن‌ها به دلیلی (!) وارد کازان روسیه شده‌اند و می‌خواهند برای مدتی در آن جا اتراق کنند.

آن‌ها هنگام ورود به کازان، از آن جایی که سه مشکل مرگبار را گذرانده‌اند، بسیار خسته شده‌اند و سعی می‌کنند بازی حدسی بکنند اما در این هنگام دوباره مشکلی پیش می‌آید و آن این است که پشمک بازی حدسی را دوست ندارد و ممکن است به این دلیل بین او و چرزه تفرقه بیفتد و ...

در این بازی، چرزه یک عدد مانند $x$ انتخاب می‌کند که عضو $\left [ 1, n \right ]$ است ولی به پشمک نمی‌گوید! پشمک می تواند تعدادی عدد *در بازه‌ی $\left[1, n \right]$ *روی کاغذ بنویسد و در نهایت به چرزه بدهد. چرزه نیز پس از تحویل گرفتن کاغذ، تک تک روی تمام اعداد کاغذ دست می‌گذارد و ب.م.م $x$ و آن عدد روی کاغذ را به پشمک می‌گوید. (چرزه هیچ وقت دروغ نمی‌گوید.) سپس پشمک باید عدد را با توجه به اطلاعات داده شده پیدا کند.

پشمک که اصلا از این بازی خوشش نیامده است، از شما می‌خواهد تا برنامه‌ای برای او بنویسید تا با گرفتن عدد $n$ حداقل تعداد عدد مورد نیاز برای نوشتن روی کاغذ و هم چنین این اعداد را به او بگویید. (وگرنه سفرشان همین جا پایان می‌یابد!)

تنها نکته‌ای که باید توجه کنید، این است که پشمک ابتدا تمام اعداد را می‌نویسد سپس چرزه جواب آن‌ها را می‌دهد.

ورودی🔗

در یک خط یک عدد $n$ داده می‌شود که بدین معنا است که $1 \leq x \leq n$ .

$1\leq n \leq 100\ 000$

خروجی🔗

در خط اول خروجی یک عدد $t$ ، که حداقل تعداد اعداد ممکن برای نوشتن روی کاغذ، برای آگاهی یافتن از عدد $x$ است، نمایش داده شود.

در خط دوم نیز $t$ عدد که اعداد مورد نیاز برای پرسش هستند را به ترتیب صعودی چاپ کنید. هم چنین توجه کنید که هر عدد خروجی باید خودش در بازه‌ی $\left [1, n \right]$ باشد.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

3
3 4 5

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

1
2

توضیح:🔗

در مثال اول با امتحان کردن، می‌توان دید که پرسیدن دو عدد برای آگاهی یافتن از عدد $x$ کافی نیست؛ برای مثال اگر فقط دو عدد $\langle 3, 4\rangle$ را بنویسیم، نمی‌توانیم عدد $5$ را از عدد $1$ تشخیص بدهیم.

برای اعداد $1$ ، $2$ ، $3$ ، $4$ ، $5$ و $6$ پاسخ‌های چرزه به $\langle 3, 4, 5 \rangle$ به ترتیب برابر با $\langle 1, 1, 1 \rangle$ ، $\langle 1, 2, 1 \rangle$ ، $\langle 3, 1, 1 \rangle$ ، $\langle 1, 4, 1 \rangle$ ، $\langle 1, 1, 5 \rangle$ و $\langle 3, 2, 1 \rangle$ است که همان طور که می‌بینید، پاسخ‌ها برای هیچ دو عددی در بازه‌ی $1$ تا $6$ یکسان نیست.

+ محدودیت زمان: ۱ ثانیه + محدودین حافظه: ۶۴ مگابایت ***** ${{عدد به فارسی|3}}$ _چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن‌ها در طی جهان‌گردی‌شان با مسائلی روبه‌رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید._ ![توضیح تصویر](http://www.aftabir.com/lifestyle/images/67a9c27da3ce82b28fe597769046c406.jpg) بعد از کازان نوبت ایتالیاست! توی ایتالیا از آن جایی که مردم پنیر را از هر چیزی بیش‌تر دوست دارند، صبحانه فقط نان و پنیر می‌خورند. از آن جایی که این خوراکی محبوب علاوه بر محبوب بودن، گران هم هست، پشمک که صبح رفت تا از سر کوچه‌ی هتلشان نان بخرد، فقط توانست یک بسته‌ی پنیر $n$ تایی بخرد. ( $n$ قاچ پنیر، پنیرها در ایتالیا قاچ قاچ به فروش می‌رسند!) آن جا بود که وقتی برگشت هتل، دید چرزه ناراحت است و حسرت می‌خورد که چرا از ایران، پنیر وطنی نیاوردیم. موقع صبحانه، اولین لقمه را چرزه (اول بزرگ تر) و بعد هم پشمک می‌خورد. (و سپس به نوبت می‌چرخد.) چرزه فقط بلد است که لقمه‌هایی را درست کند و بخورد که داخلشان $a$ قاچ واحد پنیر هست! ( $a \in A$ ) و پشمک هم فقط بلد است لقمه‌هایی درست کند و بخورد که داخلشان $b$ قاچ واحد پنیر هست! ( $b \in B$ ) لقمه ‌ی شرمندگی، در فرهنگ ایرانی به آخرین لقمه‌ای که از غذا خورده می‌شود، گفته می‌شود! و پس از آن یا هیچی از غذا نمی‌ماند و یا مقداری نیست که بشود از آن استفاده کرد. از آن‌جایی که چرزه و پشمک در این یک مدت سفر حسابی مثل ایتالیایی‌ها شدند، هیچ لقمه‌ای را بدون پنیر نمی‌خورند و از آن جایی که این دو نفر، احترام خاصی برای هم قائلند هیچ کدام نمی‌خواهند که کسی باشند که لقمه‌ی شرمندگی را بر می دارد. اگر آن‌ها به طور هوشمندانه لقمه ها را بردارند به طوری که کسی نباشند که لقمه‌ی شرمندگی را بر می‌دارد، چه کسی لقمه‌ی شرمندگی را بر می‌دارد؟ # ورودی در خط اول یک عدد $n$ که تعداد قاچ‌های پنیر است، داده می‌شود. در خط دوم یک عدد $|A|$ داده می شود که طول مجموعه‌ی چرزه است. در خط سوم $|A|$ عدد داده می شود که اعداد مجموعه‌ی چرزه هستند. در خط چهارم یک عدد $|B|$ داده می‌شود که طول مجموعه‌ی پشمک هست. در خط آخر نیز $|B|$ عدد داده می‌شود که اعداد مجموعه‌ی پشمک هستند. **تضمین می‌شود که حتما حداقل یک لقمه برداشته می‌شود. هم‌چنین توجه کنید که ممکن است که در دنباله‌ی قاچ‌های ممکن، اعداد برابر هم وجود داشته باشد؛ این بدین معنا است که مثلاً چرزه یا پشمک می توانند تعدادی قاچ پنیر را به روش‌های مختلف بر دارند!** $$1 \leq n \leq 100\ 000$$ $$1 \leq |A|, |B| \leq 100$$ $$1 \leq A_i,B_i \leq 100\ 000$$ # خروجی اگر چرزه، لقمه‌ی شرمندگی را بر می‌داشت، عبارت `Charze` و در غیر این صورت عبارت `Pashmak` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 2 1 1 ``` ## خروجی نمونه ۱ ``` Pashmak ``` ## ورودی نمونه ۲ ``` 6 2 35 1 1 4 ``` ## خروجی نمونه ۲ ``` Charze ```

مسئله‌ی صبحانه

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

${{عدد به فارسی|3}}$

توضیح تصویر

بعد از کازان نوبت ایتالیاست!

توی ایتالیا از آن جایی که مردم پنیر را از هر چیزی بیش‌تر دوست دارند، صبحانه فقط نان و پنیر می‌خورند. از آن جایی که این خوراکی محبوب علاوه بر محبوب بودن، گران هم هست، پشمک که صبح رفت تا از سر کوچه‌ی هتلشان نان بخرد، فقط توانست یک بسته‌ی پنیر $n$ تایی بخرد. ( $n$ قاچ پنیر، پنیرها در ایتالیا قاچ قاچ به فروش می‌رسند!)

آن جا بود که وقتی برگشت هتل، دید چرزه ناراحت است و حسرت می‌خورد که چرا از ایران، پنیر وطنی نیاوردیم.

موقع صبحانه، اولین لقمه را چرزه (اول بزرگ تر) و بعد هم پشمک می‌خورد. (و سپس به نوبت می‌چرخد.) چرزه فقط بلد است که لقمه‌هایی را درست کند و بخورد که داخلشان $a$ قاچ واحد پنیر هست! ( $a \in A$ ) و پشمک هم فقط بلد است لقمه‌هایی درست کند و بخورد که داخلشان $b$ قاچ واحد پنیر هست! ( $b \in B$ )

لقمه ‌ی شرمندگی، در فرهنگ ایرانی به آخرین لقمه‌ای که از غذا خورده می‌شود، گفته می‌شود! و پس از آن یا هیچی از غذا نمی‌ماند و یا مقداری نیست که بشود از آن استفاده کرد.

از آن‌جایی که چرزه و پشمک در این یک مدت سفر حسابی مثل ایتالیایی‌ها شدند، هیچ لقمه‌ای را بدون پنیر نمی‌خورند و از آن جایی که این دو نفر، احترام خاصی برای هم قائلند هیچ کدام نمی‌خواهند که کسی باشند که لقمه‌ی شرمندگی را بر می دارد. اگر آن‌ها به طور هوشمندانه لقمه ها را بردارند به طوری که کسی نباشند که لقمه‌ی شرمندگی را بر می‌دارد، چه کسی لقمه‌ی شرمندگی را بر می‌دارد؟

ورودی🔗

در خط اول یک عدد $n$ که تعداد قاچ‌های پنیر است، داده می‌شود.

در خط دوم یک عدد $|A|$ داده می شود که طول مجموعه‌ی چرزه است.

در خط سوم $|A|$ عدد داده می شود که اعداد مجموعه‌ی چرزه هستند.

در خط چهارم یک عدد $|B|$ داده می‌شود که طول مجموعه‌ی پشمک هست.

در خط آخر نیز $|B|$ عدد داده می‌شود که اعداد مجموعه‌ی پشمک هستند.

تضمین می‌شود که حتما حداقل یک لقمه برداشته می‌شود. هم‌چنین توجه کنید که ممکن است که در دنباله‌ی قاچ‌های ممکن، اعداد برابر هم وجود داشته باشد؛ این بدین معنا است که مثلاً چرزه یا پشمک می توانند تعدادی قاچ پنیر را به روش‌های مختلف بر دارند!

$1 \leq n \leq 100\ 000$ $1 \leq |A|, |B| \leq 100$ $1 \leq A_i,B_i \leq 100\ 000$

خروجی🔗

اگر چرزه، لقمه‌ی شرمندگی را بر می‌داشت، عبارت Charze و در غیر این صورت عبارت Pashmak را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

Pashmak

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

Charze

+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** _چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن‌ها در طی جهان‌گردی‌شان با مسائلی روبه‌رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید._ ![توضیح تصویر](http://s8.picofile.com/file/8280859734/vakonesh_com_cf9e864470a6715880d8fb7584358dd6.jpg) هنگام ورود به عراق، بزرگ‌ترین مشکل چرزه و پشمک به وجود آمده بود و آن این بود که داعشی‌ها جان چرزه را گرفته بودند. از آن‌جایی که چرزه یک آدم الگوریتمی است، جان او به صورت یک دنباله‌ی $n$ تایی خفن است. اما به چه دنباله‌ای خفن می گوییم؟ قبل از دانستن دنباله‌ی خفن باید تعریف دنباله‌ی چراهام پل را بدانید. فرض کنید که یک دنباله از اعداد طبیعی مانند $a$ داشته باشیم. از روی این دنباله یک دنباله از اعداد حسابی به نام $t$ به این صورت می‌سازیم که $t_i$ برابر است با تعداد $a_j$ ها به صورتی که: + $i \neq j$ + $gcd(a_i,a_j) = 1$ برای مثال اگر دنباله‌ی $a$ ما $\left[1, 3,6 \right]$ باشد، دنباله‌ی $t$، $\left[2, 1, 1 \right]$ می‌باشد. در این جا می‌گوییم دنباله‌ی $t$ دنباله‌ی چراهام پل دنباله‌ی $a$ است. اکنون به دنباله‌ی خفن باز می‌گردیم؛ یک دنباله **از اعداد حسابی** خفن است اگر و تنها اگر که بتوان آن را به صورت دنباله‌ی چراهام پل **حداقل $1381$** دنباله از اعداد طبیعی نوشت؛ یعنی یک دنباله از اعداد حسابی مانند $z$ خفن است اگر و تنها اگر حداقل $1381$ دنباله از اعداد طبیعی مانند $tmp$ وجود داشته باشد که دنباله‌ی چراهام پل $tmp$، دنباله‌ی $z$ باشد. برای مثال دنباله‌ی $\left[2, 1, 1 \right]$ یک دنباله‌ی خفن است. داعشی‌ها که می‌خواستند چرزه را آزار بدهند، به او گفتند که اگر به مساله‌‌شان پاسخ بدهد، جان او را بهش پس می دهند. اما چون چرزه جان ندارد نمی‌تواند خوب فکر کند، پشمک هم که برنامه‌نویسی زیاد بلد نیست بنابراین حل سوال داعشی‌ها به شما واگذار می‌شود: یک‌دنباله از اعداد حسابی (که ممکن است خفن نباشد) به شما می‌دهیم. شما باید حداکثر تعداد دنباله‌های زیرینه‌ی دو به دو متفاوت از این دنباله را بگویید که خودشان خفن هستند! توجه کنید که دو دنباله‌ی $a$ و $b$ متفاوت هستند اگر و تنها اگر $\sum a_i$ با $\sum b_i$ متفاوت باشد. هم چنین دنباله‌ی $a$ زیرینه‌ی دنباله‌ی $b$ است، اگر و تنها اگر سه شرط زیر برقرار باشد: 1. دنباله‌ی $a$ و $b$ متفاوت باشند. 2. داشته باشیم $|a| = |b|$ 3. به ازای هر $1 \leq i \leq |a|$ داشته باشیم $a_i \leq b_i$ # ورودی در خط اول یک عدد $n$ داده می‌شود که طول دنباله‌ی داعشی‌ها است. در خط بعد $n$ عدد حسابی داده می‌شود که دنباله‌ی داعشی‌ها است. (یعنی دنباله‌ی $a$) $$1 \leq n \leq 3000$$ $$ 0 \leq a_i \leq 10^{9}$$ # خروجی در یک خط حداکثر تعداد دنباله‌های دو به دو متفاوت خفن زیرینه‌ی دنباله‌ی ورودی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 2 1 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 3 1 0 1 ``` ## خروجی نمونه ۲ ``` 1 ``` ## توضیح برای مثال اول، یک راه برای نوشتن دنباله‌های دو به دو متفاوت زیرینه‌ی خفن به این صورت است: $$\left[2, 1, 1 \right]$$ $$\left[1, 1, 0 \right]$$ $$\left[0, 0, 0 \right]$$ هم‌چنین برای مثال دوم، تنها دنباله‌ی زیرینه‌ی خفن دنباله‌ی ورودی، $$\left[0, 0, 0 \right]$$ می‌باشد.

مسئه‌ی مرگ و زندگی

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

توضیح تصویر

هنگام ورود به عراق، بزرگ‌ترین مشکل چرزه و پشمک به وجود آمده بود و آن این بود که داعشی‌ها جان چرزه را گرفته بودند.

از آن‌جایی که چرزه یک آدم الگوریتمی است، جان او به صورت یک دنباله‌ی $n$ تایی خفن است. اما به چه دنباله‌ای خفن می گوییم؟

قبل از دانستن دنباله‌ی خفن باید تعریف دنباله‌ی چراهام پل را بدانید. فرض کنید که یک دنباله از اعداد طبیعی مانند $a$ داشته باشیم. از روی این دنباله یک دنباله از اعداد حسابی به نام $t$ به این صورت می‌سازیم که $t_i$ برابر است با تعداد $a_j$ ها به صورتی که:

$i \neq j$
$gcd(a_i,a_j) = 1$

برای مثال اگر دنباله‌ی $a$ ما $\left[1, 3,6 \right]$ باشد، دنباله‌ی $t$ ، $\left[2, 1, 1 \right]$ می‌باشد. در این جا می‌گوییم دنباله‌ی $t$ دنباله‌ی چراهام پل دنباله‌ی $a$ است.

اکنون به دنباله‌ی خفن باز می‌گردیم؛ یک دنباله از اعداد حسابی خفن است اگر و تنها اگر که بتوان آن را به صورت دنباله‌ی چراهام پل حداقل $1381$ دنباله از اعداد طبیعی نوشت؛ یعنی یک دنباله از اعداد حسابی مانند $z$ خفن است اگر و تنها اگر حداقل $1381$ دنباله از اعداد طبیعی مانند $tmp$ وجود داشته باشد که دنباله‌ی چراهام پل $tmp$ ، دنباله‌ی $z$ باشد. برای مثال دنباله‌ی $\left[2, 1, 1 \right]$ یک دنباله‌ی خفن است.

داعشی‌ها که می‌خواستند چرزه را آزار بدهند، به او گفتند که اگر به مساله‌‌شان پاسخ بدهد، جان او را بهش پس می دهند. اما چون چرزه جان ندارد نمی‌تواند خوب فکر کند، پشمک هم که برنامه‌نویسی زیاد بلد نیست بنابراین حل سوال داعشی‌ها به شما واگذار می‌شود:

یک‌دنباله از اعداد حسابی (که ممکن است خفن نباشد) به شما می‌دهیم. شما باید حداکثر تعداد دنباله‌های زیرینه‌ی دو به دو متفاوت از این دنباله را بگویید که خودشان خفن هستند!

توجه کنید که دو دنباله‌ی $a$ و $b$ متفاوت هستند اگر و تنها اگر $\sum a_i$ با $\sum b_i$ متفاوت باشد.

هم چنین دنباله‌ی $a$ زیرینه‌ی دنباله‌ی $b$ است، اگر و تنها اگر سه شرط زیر برقرار باشد:

دنباله‌ی $a$ و $b$ متفاوت باشند.
داشته باشیم $|a| = |b|$
به ازای هر $1 \leq i \leq |a|$ داشته باشیم $a_i \leq b_i$

ورودی🔗

در خط اول یک عدد $n$ داده می‌شود که طول دنباله‌ی داعشی‌ها است.

در خط بعد $n$ عدد حسابی داده می‌شود که دنباله‌ی داعشی‌ها است. (یعنی دنباله‌ی $a$ ) $1 \leq n \leq 3000$ $0 \leq a_i \leq 10^{9}$

خروجی🔗

در یک خط حداکثر تعداد دنباله‌های دو به دو متفاوت خفن زیرینه‌ی دنباله‌ی ورودی را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3
2 2 1

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

3
1 0 1

خروجی نمونه ۲🔗

توضیح🔗

برای مثال اول، یک راه برای نوشتن دنباله‌های دو به دو متفاوت زیرینه‌ی خفن به این صورت است:

$\left[2, 1, 1 \right]$ $\left[1, 1, 0 \right]$ $\left[0, 0, 0 \right]$

هم‌چنین برای مثال دوم، تنها دنباله‌ی زیرینه‌ی خفن دنباله‌ی ورودی،

$\left[0, 0, 0 \right]$

می‌باشد.

+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ***** *چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن ها در طی جهان‌گردی‌شان با مسائلی روبه رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید.* ![توضیح تصویر](http://s9.picofile.com/file/8280860950/mard.jpg) هنگام ورود به تهران، وقتی که چرزه و پشمک دیگر فکر می‌کردند که کارشان را با موفقیت انجام داده‌اند، ناگهان $q$ مرد خشمگین ظاهر شدند و از آن دو (که دیگر حسابی معروف شده‌بودند!) خواستند که بهشان یادگاری بدهند. چرزه و پشمک که می‌دانستند اگر یادگاری ندهند، حتما می‌میرند، بنابراین تصمیم گرفتند که یک دنباله از اعداد طبیعی به طول $n$ به عنوان یادگاری به آن ها بدهند. وقتی که چرزه و پشمک این را به آن $q$ مرد خشمگین گفتند، هرکدام از آن ها یک خواهش از چرزه و پشمک کردند. هر خواهش با سه عدد $l$ و $r$ و $k$ بیان می شود و این بدین معنا است که آن فرد خشمگین می‌خواهد که آنتروپرولارت دنباله‌ی $a_l, a_{l+1}, a_{l+2}, ..., a_r$ دقیقا برابر با $k$ باشد. (فرض کنید که دنباله‌ی $a$، یادگاری چرزه و پشمک باشد.) توجه کنید که آنتروپرولارت یک دنباله، برابر با کمینه‌ی تعداد زیردنباله‌هایی است که این شرایط را رعایت بکنند: 1. هر عضو از دنباله در **دقیقا یکی** از زیردنباله‌ها باشد. 2. اعداد هر زیردنباله به ترتیب اکیدا صعودی باشند. برای مثال آنتروپرولارت دنباله‌ی $\left[5, 7, 2, 3, 1 \right]$ برابر با $3$ می‌باشد و زیردنباله‌های متوالی عبارت هستند از: $\left[5, 7\right], \left[2, 3 \right], \left[1 \right]$ چرزه و پشمک می‌دانند که محبوبیت آنتروپرولارت جوری است که اگر به این خواهش‌ها توجه نشود، آن افراد آن‌ها را خواهند کشت. (این اصل به عنوان یک اصل معروف در کتاب زمینه‌ی جامعه شناسی اگ برن و نیم کف آورده‌شده‌است!) بنابراین آن ها تصمیم دارند که دنباله‌ای بسازند که به تمام این خواهش‌ها توجه شود. هم چنین از آن‌جایی که احتمالا تا الان فهمیده‌اید پشمک و چرزه کمی تنبل هستند و حال ندارند اعداد بزرگ را بنویسند بنابراین آن‌ها دنباله‌ای را با این شرایط می‌خواهند که $\max_{1 \leq i \leq |a|} a_i$ کمینه باشد. اما آن ها وقت ندارند که دنباله را خودشان بنویسند بنابراین ... # ورودی در خط اول دو عدد $n$ و $q$ آورده‌شده‌است که به ترتیب نمایانگر طول دنباله‌ی خواسته‌شده و تعداد افراد خشمگین است. در $q$ خط بعد، در هر خط به ترتیب از چپ به راست سه عدد $l$ و $r$ و $k$ داده می‌شود که نمایانگر خواهش فرد $i$ ام است. $$1 \leq n \leq 200$$ $$1 \leq q \leq \frac{n*(n+1)}{2} $$ $$1 \leq l \leq r \leq n, 1 \leq k \leq n$$ # خروجی اگر هیچ روشی برای درست کردن چنین دنباله‌ای نیست، عبارت `-1` را چاپ کنید در غیر این‌صورت در یک خط $n$ عدد چاپ کنید که دنباله‌ای است که به تمام خواهش‌ها پاسخ بدهد و بزرگ‌ترین عدد در آن، کمینه‌ی ممکن باشد. ** از آن جایی که ممکن است برای یک حالت، چندین جواب وجود داشته باشد شما، یکی را به دلخواه چاپ کنید!** # مثال ## ورودی نمونه ۱ ``` 3 3 1 2 2 1 3 2 2 3 1 ``` ## خروجی نمونه ۱ ``` 1 1 2 ``` ## ورودی نمونه ۲ ``` 4 2 1 2 1 1 3 3 ``` ## خروجی نمونه ۲ ``` -1 ```

مسئله‌ی q مرد خشمگین!

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

چرزه و پشمک اخیرا کوله‌های خود را بسته‌اند و تصمیم گرفته‌اند که دنیا را در ۷۹ روز طی کنند. اما آن ها در طی جهان‌گردی‌شان با مسائلی روبه رو می‌شوند و از شما می‌خواهند که آن‌ها را برایشان حل کنید.

توضیح تصویر

هنگام ورود به تهران، وقتی که چرزه و پشمک دیگر فکر می‌کردند که کارشان را با موفقیت انجام داده‌اند، ناگهان $q$ مرد خشمگین ظاهر شدند و از آن دو (که دیگر حسابی معروف شده‌بودند!) خواستند که بهشان یادگاری بدهند. چرزه و پشمک که می‌دانستند اگر یادگاری ندهند، حتما می‌میرند، بنابراین تصمیم گرفتند که یک دنباله از اعداد طبیعی به طول $n$ به عنوان یادگاری به آن ها بدهند. وقتی که چرزه و پشمک این را به آن $q$ مرد خشمگین گفتند، هرکدام از آن ها یک خواهش از چرزه و پشمک کردند. هر خواهش با سه عدد $l$ و $r$ و $k$ بیان می شود و این بدین معنا است که آن فرد خشمگین می‌خواهد که آنتروپرولارت دنباله‌ی $a_l, a_{l+1}, a_{l+2}, ..., a_r$ دقیقا برابر با $k$ باشد. (فرض کنید که دنباله‌ی $a$ ، یادگاری چرزه و پشمک باشد.)

توجه کنید که آنتروپرولارت یک دنباله، برابر با کمینه‌ی تعداد زیردنباله‌هایی است که این شرایط را رعایت بکنند:

هر عضو از دنباله در دقیقا یکی از زیردنباله‌ها باشد.
اعداد هر زیردنباله به ترتیب اکیدا صعودی باشند.

برای مثال آنتروپرولارت دنباله‌ی $\left[5, 7, 2, 3, 1 \right]$ برابر با $3$ می‌باشد و زیردنباله‌های متوالی عبارت هستند از:

$\left[5, 7\right], \left[2, 3 \right], \left[1 \right]$

چرزه و پشمک می‌دانند که محبوبیت آنتروپرولارت جوری است که اگر به این خواهش‌ها توجه نشود، آن افراد آن‌ها را خواهند کشت. (این اصل به عنوان یک اصل معروف در کتاب زمینه‌ی جامعه شناسی اگ برن و نیم کف آورده‌شده‌است!) بنابراین آن ها تصمیم دارند که دنباله‌ای بسازند که به تمام این خواهش‌ها توجه شود. هم چنین از آن‌جایی که احتمالا تا الان فهمیده‌اید پشمک و چرزه کمی تنبل هستند و حال ندارند اعداد بزرگ را بنویسند بنابراین آن‌ها دنباله‌ای را با این شرایط می‌خواهند که $\max_{1 \leq i \leq |a|} a_i$ کمینه باشد. اما آن ها وقت ندارند که دنباله را خودشان بنویسند بنابراین ...

ورودی🔗

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

در $q$ خط بعد، در هر خط به ترتیب از چپ به راست سه عدد $l$ و $r$ و $k$ داده می‌شود که نمایانگر خواهش فرد $i$ ام است. $1 \leq n \leq 200$ $1 \leq q \leq \frac{n*(n+1)}{2}$ $1 \leq l \leq r \leq n, 1 \leq k \leq n$

خروجی🔗

اگر هیچ روشی برای درست کردن چنین دنباله‌ای نیست، عبارت -1 را چاپ کنید در غیر این‌صورت در یک خط $n$ عدد چاپ کنید که دنباله‌ای است که به تمام خواهش‌ها پاسخ بدهد و بزرگ‌ترین عدد در آن، کمینه‌ی ممکن باشد.

** از آن جایی که ممکن است برای یک حالت، چندین جواب وجود داشته باشد شما، یکی را به دلخواه چاپ کنید!**

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

1 1 2

ورودی نمونه ۲🔗

4 2
1 2 1
1 3 3

خروجی نمونه ۲🔗

-1