ام‌سین

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

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

ورودی🔗

ورودی تنها شامل یک خط است که در آن یک عدد طبیعی $m$ آمده است. $1 \le m \le 7$

خروجی🔗

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

مثال🔗

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

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

sib
samanoo

بتایپ

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

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

ورودی🔗

در تنها خط ورودی یک رشته $S$ آمده‌است که همان رشته نوشته‌شده توسط پاشا است.

$1 \le |S| \le 100\ 000$

رشته $S$ تنها از حروف کوچک انگلیسی و = تشکیل شده‌است.

خروجی🔗

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

مثال🔗

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

sall=am

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

salam

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

testtwoo===wo

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

testtwo

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علیش که دیگه از این زندگی خسته‌شده داره میره اونور و امشب گودبای پارتیشه. پاشا هم که علاقه زیادی به پیش‌خدمت بودن داره پیش‌خدمت دم دره و به علیش کمک می‌کنه. مهمونی ساعت `00:00` شروع میشه و تا ساعت `23:59` طول می‌کشه. وظیفه پاشا اینه که هر کسی که میاد تو مهمونی و یا بیرون می‌ره، رو یه تیکه کاغذ اول اسم اون نفرو، بعدش ساعت اون موقع و بعدش `+` یا `-` (که `+` یعنی اومده و `-` یعنی رفته) رو می‌نویسه و کاغذو می‌ندازه تو کیسه. علیش بعد این که مهمونی تموم‌شد به این فکر می‌کنه که تو چه زمانی مهمونی شلوغ‌ترین موقع ممکن بوده و چون وسط مهمونی حواسش به دور و برش نبوده این سوالو از پاشا می‌پرسه. پاشا هم که یه پیش‌خدمت سادست همه‌چی رو یادش رفته و فقط اطلاعات روی کاغذها رو داره. از طرفی اون نمی‌خواد علیش‌رو ناراحت کنه و از شما می‌خواد تا با گرفتن اطلاعات روی کاغذها بگید که تو چه زمانی مهمونی شلوغ‌ترین حالت رو داشته. (تعداد افرادی که در یک زمان در مهمانی هستند بعد از تمام داخل و خارج شدن ها در آن زمان حساب می‌شود.) # ورودی در خط اول $n$ تعداد تیکه کاغذها آمده سپس در $n$ خط بعدی اسم و ساعت و یکی از کاراکترهای `+` یا `-` آمده‌است. $$1 \le n \le 100\ 000$$ + فرمت تمام ساعت‌ها به‌شکل `HH:MM` است. + اسم رشته‌ای تشکیل‌شده از حروف کوچک انگلیسی است. + تضمین می‌شود جمع طول اسم‌ها حداکثر $500\ 000$ باشد. + تضمین می‌شود اگر کسی وارد مهمانی شود، قبل از آن در مهمانی نبوده و اگر هم خارج‌شود قبل از آن در مهمانی بوده‌است. # خروجی در تنها خط خروجی شلوغ‌ترین ساعت مهمونی رو با فرمت `HH:MM` چاپ‌کنید. در صورت وجود چندین جواب یکی‌را به دلخواه چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 ali 23:32 - ali 20:12 + ``` ## خروجی نمونه ۱ ``` 21:15 ``` هر ساعتی بین $20:12$ تا $23:31$ نیز می‌تواند جواب باشد. ## ورودی نمونه ۲ ``` 4 alish 16:15 + pasha 22:34 - alish 23:56 - pasha 21:21 + ``` ## خروجی نمونه ۲ ``` 21:33 ```

چیهمونی؟

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

علیش که دیگه از این زندگی خسته‌شده داره میره اونور و امشب گودبای پارتیشه. پاشا هم که علاقه زیادی به پیش‌خدمت بودن داره پیش‌خدمت دم دره و به علیش کمک می‌کنه. مهمونی ساعت 00:00 شروع میشه و تا ساعت 23:59 طول می‌کشه.

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

ورودی🔗

در خط اول $n$ تعداد تیکه کاغذها آمده سپس در $n$ خط بعدی اسم و ساعت و یکی از کاراکترهای + یا - آمده‌است.

$1 \le n \le 100\ 000$

فرمت تمام ساعت‌ها به‌شکل HH:MM است.
اسم رشته‌ای تشکیل‌شده از حروف کوچک انگلیسی است.
تضمین می‌شود جمع طول اسم‌ها حداکثر $500\ 000$ باشد.
تضمین می‌شود اگر کسی وارد مهمانی شود، قبل از آن در مهمانی نبوده و اگر هم خارج‌شود قبل از آن در مهمانی بوده‌است.

خروجی🔗

در تنها خط خروجی شلوغ‌ترین ساعت مهمونی رو با فرمت HH:MM چاپ‌کنید. در صورت وجود چندین جواب یکی‌را به دلخواه چاپ کنید.

مثال🔗

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

2
ali 23:32 -
ali 20:12 +

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

21:15

هر ساعتی بین $20:12$ تا $23:31$ نیز می‌تواند جواب باشد.

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

4
alish 16:15 +
pasha 22:34 -
alish 23:56 -
pasha 21:21 +

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

21:33

کادوی‌درختی

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

مغازه هفت‌دال فروشی(!) به علیش یه درخت(گرافی همبند و بدون دور) $n$ راسی انداخت. روی راس $i$ ام درخت میوه‌ای به وزن $w_i$ هست. اون قراره یه زیر درخت(زیر مجموعه‌ای از رئوس درخت که همبندن) از این درخت رو انتخاب کنه و بده به پاشا. پاشا هم زیر درختی رو دوست داره که OR منطقی وزن میوه‌هاش مساوی $k$ باشه. حالا علیش که پاشا رو از ته‌ دل دوست داره می‌خواد بدونه به چند حالت می‌تونه زیردرختی رو انتخاب کنه که پاشا دوست داشته باشه. بهش کمک کنید و باقی مانده این عدد رو بر $10^9+7$ چاپ کنید.

ورودی🔗

در خط اول ورودی $n$ و $k$ آمده‌است. در خط بعدی $n$ عدد آمده که با فاصله از هم جدا شده اند و عدد $i$ ام $w_i$ است. در $n-1$ خط بعدی دو عدد $v$ و $u$ آمده که نشان‌دهنده این است که راس $v$ به راس $u$ وصل است.

$1 \le n \le 100\ 000$ $0 \le w_i , k \le 500$

تضمین می‌شود گراف داده شده درخت باشد.

خروجی🔗

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

مثال🔗

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

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

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

5 10
10 2 8 10 4
1 2
2 3
1 4
4 5

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

مستطیل‌کادویی

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

پاشا با کادوی سوال قبلش رفت به مغازه هفت‌شین فروشی(!) و یه شکلات خرید. شکلاتی که اون خریده یه مستطیل $n*m$ هست که بعضی از تیکه هاش گردو داره.

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

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

ورودی🔗

خط اول ورودی شامل $n$ و $m$ است که با فاصله از هم جدا شده‌اند.

در $n$ خط بعدی شکلات پاشا نشون داده شده که در هر خط رشته‌ای به طول $m$ آمده که از . و * تشکیل شده. * به معنای تیکه گردو دار و . به معنای تیکه عادیه.

$1 \le n, m \le 2\ 500$

خروجی🔗

در خروجی تنها تعداد زیرمستطیل های دلخواه علیش چاپ شود.

مثال🔗

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

3 2
.*
..
*.

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

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

2 2
.*
*.

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

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

4 4
.**.
..**
**..
..*.

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ممل علیشو مجبور کرده که $n$ تا رشته از حروف کوچک انگلیسی رو، رو یه کاغذ بنویسه. ممل می‌خواد این کاغذو بذاره جلو پاشا و بهش بگه با این کلمه‌ها یه رشته‌ی پالیندروم(رشته ای که خودش با برعکس برابره مثل `abba`) بنویسه. پاشا باید حداقل یکی از این رشته‌هارو استفاده کنه و می‌تونه یه رشته رو چند بار استفاده کنه و به هر ترتیبی که خواست اونارو بچسبونه به هم و بنویسه و نتیجه باید رشته‌ای پالیندروم بشه. ممل به تعداد حروفی که پاشا در رشته آخر نوشته علیشو می‌زنه. علیش رشته‌هایی که نوشته بودو یادشه و می‌خواد بدونه حداقل چند بار کتک می‌خوره. حداقل تعداد کتک‌هایی که علیش می‌خوره چند تاست؟‌ اگه پاشا نتونه رشته پالیندروم بسازه ممل علیشو ماچ می‌کنه که معادل `-1` بار(!) کتک خوردنه. # ورودی در خط اول $n$، و در $n$ خط بعدی رشته هایی که علیش نوشته آمده. تضمین می‌شود رشته‌ها فقط از حروف کوچک انگلیسی تشکیل شده باشند و جمع طول آنها حداکثر $3\ 000$ باشد. $$1 \le n \le 3\ 000$$ # خروجی در خروجی تنها حداقل تعداد بار‌هایی که علیش کتک می‌خوره رو چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 ps as sp ``` ## خروجی نمونه ۱ ``` 4 ``` \**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داره `pssp` است. ## ورودی نمونه ۲ ``` 4 abb ba bba abaa ``` ## خروجی نمونه ۲ ``` 5 ``` \**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داشته باشه `abbba` است. ## ورودی نمونه ۳ ``` 3 abbs sbbx we ``` ## خروجی نمونه ۳ ``` -1 ``` \**پاشا نمی‌تونه رشته پالیندرومی بسازه.

پاشاشاپا

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

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

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

ممل به تعداد حروفی که پاشا در رشته آخر نوشته علیشو می‌زنه. علیش رشته‌هایی که نوشته بودو یادشه و می‌خواد بدونه حداقل چند بار کتک می‌خوره. حداقل تعداد کتک‌هایی که علیش می‌خوره چند تاست؟‌ اگه پاشا نتونه رشته پالیندروم بسازه ممل علیشو ماچ می‌کنه که معادل -1 بار(!) کتک خوردنه.

ورودی🔗

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

$1 \le n \le 3\ 000$

خروجی🔗

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

مثال🔗

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

3
ps
as
sp

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

**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داره pssp است.

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

4
abb
ba
bba
abaa

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

**رشته‌ی پالیندرومی که پاشا می‌تونه بسازه و کمترین طول رو داشته باشه abbba است.

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

3
abbs
sbbx
we

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

-1

**پاشا نمی‌تونه رشته پالیندرومی بسازه.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- علیش که دیگه هدفی واسه زندگی‌کردن نداره تصمیم گرفته مریض‌شه. اما آقا مجید (که داره دکتر می‌شه) بهش گفته که باید $n$ تا قرص بخوره. علیش هم که به این سادگی نمی‌خواد قبول کنه $m$ تا شرط واسه قرص خوردن داره که هر شرط شامل $a_i$ و $b_i$ است که یعنی قرص $a_i$ام رو باید قبل قرص $b_i$ام بخوره. هم‌چنین $n$ شرط دیگه هم داره که قرص $i$ام باید حداقل $l_i$امین و حداکثر $r_i$امین قرصی باشه که می‌خوره. یه ترتیبی به علیش بدید که اگه به این ترتیب قرصاشو بخوره همه شرط‌ها برقرار باشه. # ورودی در خط اول $n$ و $m$ آمده که با یک فاصله از هم جدا شده‌اند. در $n$ خط بعدی $l_i$ و $r_i$ ها آمده‌است. در $m$ خط بعدی دو عدد $a_i$ و $b_i$ آمده که با فاصله از هم جدا شده اند و یعنی قرص $a_i$ام باید قبل قرص $b_i$ام خورده شود. $$1 \le n \le 200\ 000$$ $$1 \le m \le 300\ 000$$ $$1 \le l_i \le r_i \le n$$ $$ 1 \le a_i \le b_i \le n$$ # خروجی در خروجی $n$ خط که شامل جایگشتی از اعداد ۱ تا $n$ است و تمام شروط در آن برقرار است چاپ شود. اگر چند جواب وجود داشت یکی را به دلخواه چاپ نمایید. اگر ترتیبی وجود نداشت که همه شرط‌ها در آن برقرار باشند `-1` چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 4 2 2 1 4 1 4 1 4 1 2 1 3 3 4 2 4 ``` ## خروجی نمونه ۱ ``` -1 ``` ## ورودی نمونه ۲ ``` 4 4 1 1 2 4 2 4 4 4 1 2 2 3 3 4 1 4 ``` ## خروجی نمونه ۲ ``` 1 2 3 4 ``` ## ورودی نمونه ۳ ``` 4 3 1 1 1 4 2 3 1 4 1 2 4 3 3 2 ``` ## خروجی نمونه ۳ ``` 1 4 3 2 ```

تاکسیک‌علیش

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

علیش که دیگه هدفی واسه زندگی‌کردن نداره تصمیم گرفته مریض‌شه. اما آقا مجید (که داره دکتر می‌شه) بهش گفته که باید $n$ تا قرص بخوره. علیش هم که به این سادگی نمی‌خواد قبول کنه $m$ تا شرط واسه قرص خوردن داره که هر شرط شامل $a_i$ و $b_i$ است که یعنی قرص $a_i$ ام رو باید قبل قرص $b_i$ ام بخوره. هم‌چنین $n$ شرط دیگه هم داره که قرص $i$ ام باید حداقل $l_i$ امین و حداکثر $r_i$ امین قرصی باشه که می‌خوره. یه ترتیبی به علیش بدید که اگه به این ترتیب قرصاشو بخوره همه شرط‌ها برقرار باشه.

ورودی🔗

در خط اول $n$ و $m$ آمده که با یک فاصله از هم جدا شده‌اند.

در $n$ خط بعدی $l_i$ و $r_i$ ها آمده‌است.

در $m$ خط بعدی دو عدد $a_i$ و $b_i$ آمده که با فاصله از هم جدا شده اند و یعنی قرص $a_i$ ام باید قبل قرص $b_i$ ام خورده شود.

$1 \le n \le 200\ 000$ $1 \le m \le 300\ 000$ $1 \le l_i \le r_i \le n$ $1 \le a_i \le b_i \le n$

خروجی🔗

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

مثال🔗

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

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

-1

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

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

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

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