+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- در شرکت کوئرا **۳ کیک هم اندازه** دایره‌ای برای تولد باقر خریداری شده است. خانم عبادی می‌تواند یک کیک را: + به صورت کامل به ۱ نفر بدهد. + دو قسمت کند و به ۲ نفر بدهد. + چهار قسمت کند و به ۴ نفر بدهد. توجه کنید خانم عبادی، **برای هر کیک، دقیقاً یکی از این سه عملیات** بالا را می‌تواند انجام دهد. برای مثال نمی‌توان یک نصفه کیک را مجدداً به دو قسمت برابر تقسیم کرد. در روز تولد باقر $n$ نفر در شرکت حضور خواهند داشت. به خانم عبادی کمک کنید و بگویید آیا می‌تواند روی هر کدام از این سه کیک یکی از عملیات‌های بالا را انجام دهد به طوری که در نهایت به همه این $n$ نفر **مقدار برابری** کیک برسد یا نه. # ورودی در تنها سطر ورودی عدد صحیح و مثبت $n$ داده می‌شود. $$1 \leq n \leq 12$$ # خروجی در تنها سطر خروجی در صورتی که چنین تقسیم کردنی ممکن است `YES` و در غیراینصورت `NO` را چاپ کنید. **توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.** # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` YES ``` هر سه کیک را به یک نفر می‌دهد. پس این کار شدنی است. ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` YES ``` کیک اول را به نفر اول و کیک دوم را به نفر دوم می‌دهیم. کیک سوم را هم نصف می‌کنیم و نیمی از آن را به نفر اول و نیم دیگر را به نفر دوم می‌دهیم. ## ورودی نمونه ۳ ``` 3 ``` ## خروجی نمونه ۳ ``` YES ``` سه کیک داریم و به هر کدام یک کیک می‌دهیم. ## ورودی نمونه ۴ ``` 11 ``` ## خروجی نمونه ۴ ``` NO ``` با هر تقسیم بندی با قواعد بالا انجام این کار شدنی نیست.

کیک در کوئرا

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

در شرکت کوئرا ۳ کیک هم اندازه دایره‌ای برای تولد باقر خریداری شده است.

خانم عبادی می‌تواند یک کیک را:

به صورت کامل به ۱ نفر بدهد.
دو قسمت کند و به ۲ نفر بدهد.
چهار قسمت کند و به ۴ نفر بدهد.

توجه کنید خانم عبادی، برای هر کیک، دقیقاً یکی از این سه عملیات بالا را می‌تواند انجام دهد. برای مثال نمی‌توان یک نصفه کیک را مجدداً به دو قسمت برابر تقسیم کرد.

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

ورودی🔗

در تنها سطر ورودی عدد صحیح و مثبت $n$ داده می‌شود. $1 \leq n \leq 12$

خروجی🔗

در تنها سطر خروجی در صورتی که چنین تقسیم کردنی ممکن است YES و در غیراینصورت NO را چاپ کنید.

توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.

مثال🔗

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

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

YES

هر سه کیک را به یک نفر می‌دهد. پس این کار شدنی است.

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

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

YES

کیک اول را به نفر اول و کیک دوم را به نفر دوم می‌دهیم. کیک سوم را هم نصف می‌کنیم و نیمی از آن را به نفر اول و نیم دیگر را به نفر دوم می‌دهیم.

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

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

YES

سه کیک داریم و به هر کدام یک کیک می‌دهیم.

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

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

NO

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

رشته در کوئرا

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

امیرحسین دستور ساخت یک رشته افسانه‌ای را پیدا کرده‌است. برای ساخت این رشته باید مقدار $n$ را انتخاب کنیم و رشته $s_n$ را به این روش تولید کنیم:

اگر $n = 1$ آنگاه: $s_n = "1"$ اگر $n > 1$ آنگاه: $s_n = s_{n - 1} + "n" + s_{n - 1}$

منظور از $a + b$ برای دو رشته $a$ و $b$ ، یعنی رشته‌ای که از چسابندن $a$ در سمت چپ $b$ بدست می‌آید.

منظور از $"n"$ نمایش عدد صحیح $n$ به صورت یک رشته است.

پس با توجه به تعریف بالا داریم: $s_1 = "1"$ $s_2 = "121"$ $s_3 = "1213121"$ $...$

حال از شما می‌خواهیم مجموع ارقام نوشته شده در رشته‌ی $s_n$ را چاپ کنید. چون ممکن است این مقدار خیلی بزرگ باشد، باقی‌مانده آن را بر $10^9+7$ محاسبه کنید.

ورودی🔗

در تنها سطر اول ورودی عدد صحیح $n$ آمده است. $1 \leq n \leq 100$

خروجی🔗

در تنها سطر خروجی باقی‌مانده مجموع ارقام نوشته شده در رشته‌ی $s_n$ ، بر $10^9+7$ را چاپ کنید.

مثال🔗

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

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

رشته $s_1 = "1"$ است پس مجموع ارقام آن برابر $1$ است.

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

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

رشته $s_2 = "121"$ است پس مجموع ارقام آن برابر $1 + 2 + 1 = 4$ است.

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

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

رشته $s_3 = "1213121"$ است پس مجموع ارقام آن برابر $1 + 2 + 1 + 3 + 1 + 2 + 1 = 11$ است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- باقر می‌خواهد $n$ نامه برای $m$ شرکت مختلف بفرستد. نام این شرکت‌ها را با اعداد $1, 2, \dots, m \,$ نمایش می‌دهیم. باید نامه‌ی اول به شرکت $l_1$، نامه دوم به شرکت $l_2$ و... نامه $n$ام به شرکت $l_n$ ارسال شود. به عبارت دیگر نامه $i$ام ($1 \leq i \leq n$) باید به شرکت $l_i$ ($1 \leq l_i \leq m$) ارسال شود. باقر برای ارسال این نامه‌ها، $n$ پاکت تهیه می‌کند که روی پاکت $i$ام نشانی شرکت $l_i$ نوشته شده است. باقر به مهدی می‌گوید که نامه $i$ام را در پاکت $i$ام قرار بده و در صندوق پست بنداز. اما مهدی می‌خواهد این فرمان را به درستی انجام ندهد و کار را اساسی خراب کند. به همین دلیل تصمیم دارد طوری نامه‌ها را در پاکت‌ها قرار دهد که در هر پاکت دقیقاً یک نامه قرار بگیرد ولی **هیچ شرکتی نامه مربوط به خودش را دریافت نکند**. به مهدی کمک کنید تا بررسی کند آیا انجام چنین کاری شدنی است یا نه. # ورودی در سطر اول ورودی دو عدد صحیح و مثبت $n$ و $m$ که با فاصله از هم جدا شده‌اند، داده می‌شود. $$1 \leq m \leq n \leq 100 \, 000$$ در سطر دوم ورودی $n$ عدد صحیح و مثبت $l_1, l_2, \dots, l_n \,$ که با فاصله از هم جدا شده است آمده و شرکت مقصد نامه $i$ام را نشان می‌دهد. $$1 \leq l_i \leq m$$ تضمین می‌شود که هر کدام از اعداد $1, 2, \dots, m \,$ حداقل یکبار در این دنباله ظاهر شده‌اند. # خروجی در تنها سطر خروجی در صورتی که می‌توان طوری نامه‌ها را در پاکت‌ها گذاشت به‌طوری که هیچ‌نامه‌ای به شرکت مربوط به خودش نرسد، `YES` و در غیر این صورت `NO` چاپ کنید. **توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.** # مثال ## ورودی نمونه ۱ ``` 3 1 1 1 1 ``` ## خروجی نمونه ۱ ``` NO ``` همه نامه‌ها به شرکت ‍‍۱ است پس همه پاکت‌ها هم آدرس شرکت ۱ را دارند پس هر جایگشتی از نامه‌ها را که در پاکت‌ها قرار دهیم، همه نامه‌ها به شرکت ۱ می‌رسد و مهدی به هدفش نمی‌رسد. ## ورودی نمونه ۲ ``` 4 4 4 1 2 3 ``` ## خروجی نمونه ۲ ``` YES ``` چهار نامه برای شرکت‌های ۱ و ۲ و ۳ و ۴ و چهار پاکت با آدرس شرکت‌های ۱ و ۲ و ۳ و ۴ داریم. نامه شرکت ۱ را در پاکت شرکت ۲ و نامه شرکت ۲ را در پاکت شرکت ۱ قرار می‌دهیم. همچنین نامه شرکت ۳ را در پاکت شرکت ۴ و نامه شرکت ۴ را در پاکت شرکت ۳ قرار می‌دهیم. به این ترتیب هیچ‌نامه‌ای به شرکت مربوط به خود نمی‌رسد و مهدی به هدفش می‌رسد.

نامه‌ها در کوئرا

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

باقر می‌خواهد $n$ نامه برای $m$ شرکت مختلف بفرستد. نام این شرکت‌ها را با اعداد $1, 2, \dots, m \,$ نمایش می‌دهیم.

باید نامه‌ی اول به شرکت $l_1$ ، نامه دوم به شرکت $l_2$ و... نامه $n$ ام به شرکت $l_n$ ارسال شود. به عبارت دیگر نامه $i$ ام ( $1 \leq i \leq n$ ) باید به شرکت $l_i$ ( $1 \leq l_i \leq m$ ) ارسال شود.

باقر برای ارسال این نامه‌ها، $n$ پاکت تهیه می‌کند که روی پاکت $i$ ام نشانی شرکت $l_i$ نوشته شده است.

باقر به مهدی می‌گوید که نامه $i$ ام را در پاکت $i$ ام قرار بده و در صندوق پست بنداز. اما مهدی می‌خواهد این فرمان را به درستی انجام ندهد و کار را اساسی خراب کند. به همین دلیل تصمیم دارد طوری نامه‌ها را در پاکت‌ها قرار دهد که در هر پاکت دقیقاً یک نامه قرار بگیرد ولی هیچ شرکتی نامه مربوط به خودش را دریافت نکند.

به مهدی کمک کنید تا بررسی کند آیا انجام چنین کاری شدنی است یا نه.

ورودی🔗

در سطر اول ورودی دو عدد صحیح و مثبت $n$ و $m$ که با فاصله از هم جدا شده‌اند، داده می‌شود. $1 \leq m \leq n \leq 100 \, 000$ در سطر دوم ورودی $n$ عدد صحیح و مثبت $l_1, l_2, \dots, l_n \,$ که با فاصله از هم جدا شده است آمده و شرکت مقصد نامه $i$ ام را نشان می‌دهد. $1 \leq l_i \leq m$

تضمین می‌شود که هر کدام از اعداد $1, 2, \dots, m \,$ حداقل یکبار در این دنباله ظاهر شده‌اند.

خروجی🔗

در تنها سطر خروجی در صورتی که می‌توان طوری نامه‌ها را در پاکت‌ها گذاشت به‌طوری که هیچ‌نامه‌ای به شرکت مربوط به خودش نرسد، YES و در غیر این صورت NO چاپ کنید.

توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.

مثال🔗

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

3 1
1 1 1

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

NO

همه نامه‌ها به شرکت ‍‍۱ است پس همه پاکت‌ها هم آدرس شرکت ۱ را دارند پس هر جایگشتی از نامه‌ها را که در پاکت‌ها قرار دهیم، همه نامه‌ها به شرکت ۱ می‌رسد و مهدی به هدفش نمی‌رسد.

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

4 4
4 1 2 3

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

YES

چهار نامه برای شرکت‌های ۱ و ۲ و ۳ و ۴ و چهار پاکت با آدرس شرکت‌های ۱ و ۲ و ۳ و ۴ داریم. نامه شرکت ۱ را در پاکت شرکت ۲ و نامه شرکت ۲ را در پاکت شرکت ۱ قرار می‌دهیم. همچنین نامه شرکت ۳ را در پاکت شرکت ۴ و نامه شرکت ۴ را در پاکت شرکت ۳ قرار می‌دهیم. به این ترتیب هیچ‌نامه‌ای به شرکت مربوط به خود نمی‌رسد و مهدی به هدفش می‌رسد.

شیفت در کوئرا

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

یک رشته از حروف کوچک انگلیسی به نام $s = s_1s_2\dots s_n \,$ داریم.

منظور از یک «شیفت $s$ » یعنی انتقال دادن $k$ حرف اول این رشته به آخر آن. ( $1 \leq k \leq n \,$ )

به عبارت دیگر یک شیفت $s$ ، یک رشته به صورت زیر است:‌ $s_{k + 1} \dots s_n s_1 s_2 \dots s_k$

حال از شما می‌خواهیم با داشتن رشته $s$ ، رشته‌ای از این $n$ شیفت را پیدا کنید که در ترتیب الفبایی کمینه باشد.

در ترتیب الفبایی، رشته $a$ از رشته $b$ کمتر است اگر اولین کاراکتر $a$ که با $b$ فرق دارد، در ترتیب الفبای انگلیسی زودتر آمده باشد.

ورودی🔗

در تنها سطر ورودی یک رشته از حروف کوچک انگلیسی مثل $s$ آمده است. $1 \leq |s| \leq 100 \, 000$ منظور از $|s|$ طول رشته $s$ است.

خروجی🔗

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

مثال🔗

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

nima

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

anim

شیفت‌های nima عبارت است از iman، mani، anim و nima که رشته‌ای که در ترتیب الفبایی بین این ۴ رشته کوچک‌ترین است anim خواهد بود.

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

acabd

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

abdac

شیفت‌های acabd عبارت است از cabda، abdac، bdaca، dacab و acabd است که رشته‌ای که در ترتیب الفبایی بین این ۵ رشته کوچک‌ترین است abdac خواهد بود.

پرانتزگذاری در کوئرا

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

به یک رشته از ) و ( یک «پرانتزگذاری معتبر» می‌گوییم اگر برای هر پرانتز باز بتوان یک پرانتز بسته متناظر کرد به طوری که رشته بین این دو پرانتز تشکیل یک پرانتزگذاری معتبر دهد و با حذف این بازه رشته باقی‌مانده پرانتزگذاری معتبر باشد.

به یک پرانتز گذاری « $k$ -معتبر» می‌گوییم اگر با اضافه کردن $k$ پرانتز باز به ابتدای رشته و $k$ پرانتز بسته در انتهای آن، پرانتز گذاری معتبر شود.

تعداد رشته‌هایی را بیاید که طول آن $2n$ بوده و $k$ -معتبر باشد. چون تعداد این رشته خیلی زیاد است باقی‌مانده پاسخ مسئله را به $10^9 + 7$ چاپ کنید.

ورودی🔗

در سطر اول ورودی عدد صحیح و مثبت $t$ داده می‌شود و در $t$ سطر بعدی هر کدام دو عدد $n$ و $k$ داده می شود. $1 \le t \le 10^5$ $0 \le k \le 10^6$ $1 \le n \le 10^6$

خروجی🔗

خروجی شامل $t$ سطر است که در هر سطر تعداد رشته های به طول $2n$ که $k$ -معتبر باشد را چاپ کنید.

مثال🔗

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

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

5
62
242