+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۰۲۴ مگابایت
----------
صبا به این فکر رفته بود که تابستون خودشو چه‌جوری بگذرونه و به این نتیجه رسید که تو یه شرکت کارآموزی کنه و واسه همین تو مسابقه کارآموزشو سایت کوئرا ثبت‌نام کرد. اما اون که مقدار کمی با برنامه‌نویسی آشنایی داره حس میکنه که یه‌کم کارش واسه شرکت تو این مسابقه سخته. واسه همین تصمیم گرفت تا از یه سوال آسون برنامه‌نویسی کار رو شروع کنه که ازش خواسته برنامه زیر رو بنویسه:
در ابتدا دو عدد $n$ و $k$ به برنامه ورودی داده میشود و سپس $n$ را $k$ بار تقسیم بر ۲ می‌کند و در آخر مقدار کف جواب حاصل را به عنوان خروجی چاپ می‌کند. (کف یک عددی حقیقی مثل $a$، بزرگ‌ترین عدد صحیحی است که کوچکتر یا مساوی $a$ است.)
صبا که کمی گیج شده و حس میکنه نمی‌تونه این مسئله رو حل کنه از شما میخواد تا این مسئله رو برای او حل کنید؛ غافل از این که شما خودتون در کارآموزشو شرکت کردید و فعلا باید خودتون هم این مسئله رو حل کنید!
# ورودی
در تنها خط ورودی، دو عدد $n$ و $k$ داده میشود.
$$ -2\ 000\ 000 \le n \le 2\ 000\ 000$$
$$ 0 \le k \le 50$$
# خروجی
در تنها خط خروجی، پاسخ مسئله را چاپ کنید.
# مثال
## ورودی نمونه ۱
```
7 2
```
## خروجی نمونه ۱
```
1
```
## توضیح نمونه ۱
بعد از $2$ بار تقسیم کردن $7$ بر $2$، به عدد $1.75$ می‌رسیم که کف آن برابر $1$ میشود.
## ورودی نمونه ۲
```
-7 1
```
## خروجی نمونه ۲
```
-4
```
## توضیح نمونه ۲
بعد از $1$ بار تقسیم کردن $-7$ بر $2$، به عدد $-3.5$ می‌رسیم که کف آن برابر $-4$ میشود.
صبا و سوال ساده
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۱۰۲۴ مگابایت
صبا به این فکر رفته بود که تابستون خودشو چه‌جوری بگذرونه و به این نتیجه رسید که تو یه شرکت کارآموزی کنه و واسه همین تو مسابقه کارآموزشو سایت کوئرا ثبت‌نام کرد. اما اون که مقدار کمی با برنامه‌نویسی آشنایی داره حس میکنه که یه‌کم کارش واسه شرکت تو این مسابقه سخته. واسه همین تصمیم گرفت تا از یه سوال آسون برنامه‌نویسی کار رو شروع کنه که ازش خواسته برنامه زیر رو بنویسه:
در ابتدا دو عدد n و k به برنامه ورودی داده میشود و سپس n را k بار تقسیم بر ۲ می‌کند و در آخر مقدار کف جواب حاصل را به عنوان خروجی چاپ می‌کند. (کف یک عددی حقیقی مثل a، بزرگ‌ترین عدد صحیحی است که کوچکتر یا مساوی a است.)
صبا که کمی گیج شده و حس میکنه نمی‌تونه این مسئله رو حل کنه از شما میخواد تا این مسئله رو برای او حل کنید؛ غافل از این که شما خودتون در کارآموزشو شرکت کردید و فعلا باید خودتون هم این مسئله رو حل کنید!
بعد از 1 بار تقسیم کردن −7 بر 2، به عدد −3.5 می‌رسیم که کف آن برابر −4 میشود.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۰۲۴ مگابایت
----------
کاراکتر "من" که دید اکبر بدون اجازه از اسمش در سوال ها استفاده کرده است، تصمیم گرفت انتقام بگیرد.
در سرزمین "اکبراینا" درختی کبیر وجود داشت، درخت کبیر درختی ریشه‌دار بی نهایت راس است که هر راس آن دارای 26 فرزند است. امیرمحمد که به نام‌گذاری رئوس درخت علاقه زیادی دارد، به هر راسی از این درخت رشته‌ای از حروف کوچک انگلیسی را متناظر کرد، میدانیم نام‌گذاری امیرمحمد خاصیت های زیر را دارد:
+ به راس ریشه رشته تهی متناظر شده است.
+ به هیچ دو راسی رشته یکسان متناظر نشده است.
+ به ازای هر راسی به جز ریشه اگر رشته متناظر این راس .$s_1 s_2 s_3...s_k$ باشد، رشته متناظر پدر این راس $ s_1 s_2 s_3 ... s_{k-1} $ است.
بعد از نام‌گذاری امیرمحمد، امید به وجد آمد و رفت که از راس‌های این درخت بازدید کنه، ولی بعد از مدتی کوتاه فهمید که تو راسی به نام $O$ با یک رشته $m$ حرفی قرار داره و گم شده. برای همین به اکبر (مالک سرزمین و همچنین مالک درخت کبیر) زنگ زد و گفت: "اکبرر بیا منو پیدا کن گم شدم". اکبر که در آن لحظه در راسی به نام $A$ با $n$ حرف قرار داشت، امید خود را از دست نداد و به سمت امید دوید، او می‌توانست در هر ثانیه از یک راس به یکی از راس های مجاورش برود، و چون خیلی نگران از بین رفتن امیدش بود، در کوتاه ترین زمان ممکن امید خود را بدست آورد. حال شما به عنوان شنونده این داستان پندآموز به ما اعلام کنید که اکبر چند ثانیه پس از حرکت، امید خود را بدست می آورد.
توجه‌کنید که ساختار نام‌گذاری راس‌های درخت مانند درخت پیشوندی است که برای پیداکردن مطالب بیشتر در این مورد می‌توانید به [این‌جا](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%BE%DB%8C%D8%B4%D9%88%D9%86%D8%AF%DB%8C) مراجعه کنید.
# ورودی
در خط اول ورودی عدد $n$ آمده است.
در خط دوم ورودی رشته ی $A$ دارای $n$ حرف از حروف کوچک الفبای انگلیسی آمده است.
در خط سوم ورودی عدد $m$ آمده است.
در خط چهارم ورودی رشته ی $O$ دارای $m$ حرف از حروف کوچک الفبای انگلیسی آمده است.
$$1 \le n, m \le 100\ 000$$
# خروجی
در تنها خط خروجی یک عدد که نشان دهنده پاسخ مسئله است را چاپ کنید.
# مثال
## ورودی نمونه ۱
```
2
ab
2
ac
```
## خروجی نمونه ۱
```
2
```
اکبر در ثانیه اول از $ab$ به $a$ میرود، و در ثانیه دوم از $a$ به $ac$ میرود و امیدش با بدست می‌آورد.
## ورودی نمونه ۲
```
3
aab
3
aba
```
## خروجی نمونه ۲
```
4
```
اکبر در ثانیه اول از $aab$ به $aa$ میرود، در ثانیه دوم از $aa$ به $a$ میرود، در ثانیه سوم از $a$ به $ab$ میرود، در ثانیه چهارم از $ab$ به $aba$ میرود و امیدش با بدست می‌آورد.
اکبر در درخت کبیر
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۱۰۲۴ مگابایت
کاراکتر "من" که دید اکبر بدون اجازه از اسمش در سوال ها استفاده کرده است، تصمیم گرفت انتقام بگیرد.
در سرزمین "اکبراینا" درختی کبیر وجود داشت، درخت کبیر درختی ریشه‌دار بی نهایت راس است که هر راس آن دارای 26 فرزند است. امیرمحمد که به نام‌گذاری رئوس درخت علاقه زیادی دارد، به هر راسی از این درخت رشته‌ای از حروف کوچک انگلیسی را متناظر کرد، میدانیم نام‌گذاری امیرمحمد خاصیت های زیر را دارد:
به راس ریشه رشته تهی متناظر شده است.
به هیچ دو راسی رشته یکسان متناظر نشده است.
به ازای هر راسی به جز ریشه اگر رشته متناظر این راس .s1s2s3...sk باشد، رشته متناظر پدر این راس s1s2s3...sk−1 است.
بعد از نام‌گذاری امیرمحمد، امید به وجد آمد و رفت که از راس‌های این درخت بازدید کنه، ولی بعد از مدتی کوتاه فهمید که تو راسی به نام O با یک رشته m حرفی قرار داره و گم شده. برای همین به اکبر (مالک سرزمین و همچنین مالک درخت کبیر) زنگ زد و گفت: "اکبرر بیا منو پیدا کن گم شدم". اکبر که در آن لحظه در راسی به نام A با n حرف قرار داشت، امید خود را از دست نداد و به سمت امید دوید، او می‌توانست در هر ثانیه از یک راس به یکی از راس های مجاورش برود، و چون خیلی نگران از بین رفتن امیدش بود، در کوتاه ترین زمان ممکن امید خود را بدست آورد. حال شما به عنوان شنونده این داستان پندآموز به ما اعلام کنید که اکبر چند ثانیه پس از حرکت، امید خود را بدست می آورد.
توجه‌کنید که ساختار نام‌گذاری راس‌های درخت مانند درخت پیشوندی است که برای پیداکردن مطالب بیشتر در این مورد می‌توانید به این‌جا مراجعه کنید.
در خط اول ورودی عدد n آمده است.
در خط دوم ورودی رشته ی A دارای n حرف از حروف کوچک الفبای انگلیسی آمده است.
در خط سوم ورودی عدد m آمده است.
در خط چهارم ورودی رشته ی O دارای m حرف از حروف کوچک الفبای انگلیسی آمده است.
اکبر در ثانیه اول از aab به aa میرود، در ثانیه دوم از aa به a میرود، در ثانیه سوم از a به ab میرود، در ثانیه چهارم از ab به aba میرود و امیدش با بدست می‌آورد.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۰۲۴ مگابایت
------------------------------
**صورت سوال و ورودی‌ها در این سوال دقیقاً با ساعت‌کاری سنگین برابر است. تنها تفاوت این دو سوال، خروجی‌ای‌ست که شما بایستی چاپ کنید**.
در شرکت کوئرا $n$ نفر مشغول به کارند که جز باقر (رئیس شرکت) هر نفر بالادستی‌ای دارد. به مجموعه‌ی هر فرد و زیردستانش و زیردستانِ زیردستانش و... تیم او می‌گوییم. مثلن تیم باقر برابر کل اعضای شرکت است. در واقع ساختار شرکت شبیه یک **جنگل** (گراف جهت‌دار بدون دور) است (البته این نکته در ورژن سبک سوال تاثیری ندارد).
این روزها کوئرا با $m$ پروژه‌ی سخت و نفس‌گیر دست و پنجه نرم می‌کند. اعضای کوئرا شدیدن مشغولند و وقت سر خاراندن‌شان نیست. هر پروژه تعدادی زیرپروژه دارد. به مجموعه‌ی هر پروژه و زیرپروژه‌هایش و زیرپروژه‌های زیرپروژه‌هایش و... پراجکت‌باکس آن پروژه می‌گوییم. در واقع ساختار پروژه‌ها شبیه یک **جنگل** (گراف جهت‌دار بدون دور) است (البته این نکته در ورژن سبک سوال تاثیری ندارد).
سِپَسَک، سامانه‌ی پردازش ساعت‌های کاری، ایده‌ای بدیع از استاد باقر است که قرار است اثر چشم‌گیری در رشد و پیش‌رفت شرکت مذکور داشته باشد. داستان از این‌جا شروع میشود که شما باید این سیستم را بنویسید.
پس از گذشت چند سال از شروع به کار کوئرا هم اکنون اعضای خوش‌تلاش کوئرا همه‌ی پروژه‌ها را تحویل داده اند. باقر ساعت‌های کاری شرکت از بدو شروع به کار کوئرا را در ورودی به شما تحویل می‌دهد. شما باید در راستای تکمیل سپسک تحلیل‌هایی بر روی ساعت‌های کاری اعضای کوئرا انجام دهید.
# ورودی
در خط اول ورودی دو عدد $n$ و $m$ و $k$ آمده است که تعداد اعضای شرکت و تعداد پروژه‌ها و تعداد رکوردها را نشان می‌دهد.
در خط بعد $n-1$ عدد آمده‌ست که $i$امین آنها شماره‌ی بالادستی نفر $i+1$ام را نشان می‌دهد. دقت کنید شماره‌ی باقر ۱ می‌باشد و بالادستی ندارد.
در خط بعد $m$ عدد آمده‌ست که $i$امین آنها شماره‌ی پروژه‌ای که شامل پروژه‌ی $i$ام میشود را نشان می‌دهد. اگر پروژه‌ی دیگری شامل این پروژه نشود این عدد برابر صفر خواهد بود.
در خط بعد $m$ عدد آمده‌ست که $i$امین آنها سود پروژه‌ی $i$ام را نشان می‌دهد. دقت کنید سود هر پروژه مستقل از زیرپروژه‌های آن است.
در ادامه $k$ خط می‌آید که هر کدام یک رکورد ساعت‌کاری‌ست. هر رکورد به فرمت `YY/MM/DD hh:mm:ss Person Project Type` است که `Person` برابر شماره‌ی فرد است، `Project` شماره‌ی پروژه‌ست و `Type` برابر `Start` یا `End` است که نشان‌دهنده‌ی این است که این رکورد شروع یا پایان یک ساعت کاری را نشان می‌دهد.
$$1 \le n, m, k \le 300\ 000$$
شماره‌ی بالادستی هر نفر از خودش کوچکتر است.
شماره‌ی پروژه‌ی شامل‌شونده‌ی پروژه‌ی دیگر (در صورت وجود) از آن کوچکتر است.
کوئرا در سال ۹۴ تاسیس شد و تاریخ پیش از آن به شما داده نخواهد شد. همچنین تاریخی پس از سال ۹۷ نیز به شما داده نخواهد شد.
به طول هر ماه دقت کنید (ماه‌های بهار و تابستان ۳۱ روز، پاییز و زمستان جز اسفند ۳۰ و اسفند ۲۹ روزه‌ست). سال ۹۵ کبیسه‌ست!
هر بازه‌ای از ساعت کاری که شروع شده است لزوماً تمام هم شده است و $k$ زوج است.
سود هیچ پروژه‌ای از ۱ میلیارد بیشتر نیست.
ممکن نیست یک نفر هم‌زمان در حال انجام چند کار باشد.
# خروجی
در خط اول میزان کار انجام شده توسط اعضای شرکت را با فرمت `h:mm:ss` چاپ کنید (تعداد ارقام بخش ساعت اهمیتی ندارد، ولی اگر صفر باشد باید صفر را چاپ کنید، مثلاً اگر کسی ۱۳ دقیقه و ۱۷ ثانیه کار کرده باشد باید `0:13:17` چاپ کنید).
در خط بعد میزان کار انجام شده روی هر پروژه را با فرمت `h:mm:ss` چاپ کنید.
در خط سوم بیشترین کار انجام شده در یک روز را با فرمت `h:mm:ss` چاپ کنید.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:-------:|:----------:|:-----------:|
|۱ | ۳۰ | تنها باید خط اول از خروجی شما صحیح باشد |
|۲| ۳۰ | تنها باید خط دوم از خروجی شما صحیح باشد |
|۳| ۴۰ | تنها باید خط سوم از خروجی شما صحیح باشد |
دقت کنید شما باید دقیقاً ۳ خط چاپ کنید. به ازای درست بودن هر کدوم از این خطوط نمره‌ی مشخص شده را دریافت خواهید کرد. تست‌های ۱ و ۲ و ۳ همان ورودی نمونه هستند و در هر کدام درست بودن همان خط بررسی میشود. تست‌های ۴ و ۵ و ۶ نیز به ترتیب مربوط به خطوط ۱ و ۲ و ۳ هستند. مثلاً اگر شما خط سوم خروجی‌تان درست باشد باید تست‌های ۳ و ۶ را درست جواب بدهید.
# مثال
## ورودی نمونه
```
3 3 10
1 2
0 1 0
56 62 56
97/06/03 20:09:33 1 3 Start
97/06/03 20:19:57 3 2 Start
97/06/04 23:13:14 3 2 End
97/06/04 23:15:54 1 3 End
97/07/02 10:09:33 2 1 Start
97/07/02 10:15:54 2 1 End
97/07/03 23:09:33 1 2 Start
97/07/03 23:19:57 3 2 Start
97/07/04 01:13:14 3 2 End
97/07/04 01:15:54 1 2 End
```
## خروجی نمونه
```
29:12:42 0:06:21 28:46:34
0:06:21 30:52:55 27:06:21
46:29:08
```
ساعت‌کاری سبک
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۱۰۲۴ مگابایت
صورت سوال و ورودی‌ها در این سوال دقیقاً با ساعت‌کاری سنگین برابر است. تنها تفاوت این دو سوال، خروجی‌ای‌ست که شما بایستی چاپ کنید.
در شرکت کوئرا n نفر مشغول به کارند که جز باقر (رئیس شرکت) هر نفر بالادستی‌ای دارد. به مجموعه‌ی هر فرد و زیردستانش و زیردستانِ زیردستانش و... تیم او می‌گوییم. مثلن تیم باقر برابر کل اعضای شرکت است. در واقع ساختار شرکت شبیه یک جنگل (گراف جهت‌دار بدون دور) است (البته این نکته در ورژن سبک سوال تاثیری ندارد).
این روزها کوئرا با m پروژه‌ی سخت و نفس‌گیر دست و پنجه نرم می‌کند. اعضای کوئرا شدیدن مشغولند و وقت سر خاراندن‌شان نیست. هر پروژه تعدادی زیرپروژه دارد. به مجموعه‌ی هر پروژه و زیرپروژه‌هایش و زیرپروژه‌های زیرپروژه‌هایش و... پراجکت‌باکس آن پروژه می‌گوییم. در واقع ساختار پروژه‌ها شبیه یک جنگل (گراف جهت‌دار بدون دور) است (البته این نکته در ورژن سبک سوال تاثیری ندارد).
سِپَسَک، سامانه‌ی پردازش ساعت‌های کاری، ایده‌ای بدیع از استاد باقر است که قرار است اثر چشم‌گیری در رشد و پیش‌رفت شرکت مذکور داشته باشد. داستان از این‌جا شروع میشود که شما باید این سیستم را بنویسید.
پس از گذشت چند سال از شروع به کار کوئرا هم اکنون اعضای خوش‌تلاش کوئرا همه‌ی پروژه‌ها را تحویل داده اند. باقر ساعت‌های کاری شرکت از بدو شروع به کار کوئرا را در ورودی به شما تحویل می‌دهد. شما باید در راستای تکمیل سپسک تحلیل‌هایی بر روی ساعت‌های کاری اعضای کوئرا انجام دهید.
در خط اول ورودی دو عدد n و m و k آمده است که تعداد اعضای شرکت و تعداد پروژه‌ها و تعداد رکوردها را نشان می‌دهد.
در خط بعد n−1 عدد آمده‌ست که iامین آنها شماره‌ی بالادستی نفر i+1ام را نشان می‌دهد. دقت کنید شماره‌ی باقر ۱ می‌باشد و بالادستی ندارد.
در خط بعد m عدد آمده‌ست که iامین آنها شماره‌ی پروژه‌ای که شامل پروژه‌ی iام میشود را نشان می‌دهد. اگر پروژه‌ی دیگری شامل این پروژه نشود این عدد برابر صفر خواهد بود.
در خط بعد m عدد آمده‌ست که iامین آنها سود پروژه‌ی iام را نشان می‌دهد. دقت کنید سود هر پروژه مستقل از زیرپروژه‌های آن است.
در ادامه k خط می‌آید که هر کدام یک رکورد ساعت‌کاری‌ست. هر رکورد به فرمت YY/MM/DD hh:mm:ss Person Project Type است که Person برابر شماره‌ی فرد است، Project شماره‌ی پروژه‌ست و Type برابر Start یا End است که نشان‌دهنده‌ی این است که این رکورد شروع یا پایان یک ساعت کاری را نشان می‌دهد.
1≤n,m,k≤300000
شماره‌ی بالادستی هر نفر از خودش کوچکتر است.
شماره‌ی پروژه‌ی شامل‌شونده‌ی پروژه‌ی دیگر (در صورت وجود) از آن کوچکتر است.
کوئرا در سال ۹۴ تاسیس شد و تاریخ پیش از آن به شما داده نخواهد شد. همچنین تاریخی پس از سال ۹۷ نیز به شما داده نخواهد شد.
به طول هر ماه دقت کنید (ماه‌های بهار و تابستان ۳۱ روز، پاییز و زمستان جز اسفند ۳۰ و اسفند ۲۹ روزه‌ست). سال ۹۵ کبیسه‌ست!
هر بازه‌ای از ساعت کاری که شروع شده است لزوماً تمام هم شده است و k زوج است.
سود هیچ پروژه‌ای از ۱ میلیارد بیشتر نیست.
ممکن نیست یک نفر هم‌زمان در حال انجام چند کار باشد.
در خط اول میزان کار انجام شده توسط اعضای شرکت را با فرمت h:mm:ss چاپ کنید (تعداد ارقام بخش ساعت اهمیتی ندارد، ولی اگر صفر باشد باید صفر را چاپ کنید، مثلاً اگر کسی ۱۳ دقیقه و ۱۷ ثانیه کار کرده باشد باید 0:13:17 چاپ کنید).
در خط بعد میزان کار انجام شده روی هر پروژه را با فرمت h:mm:ss چاپ کنید.
در خط سوم بیشترین کار انجام شده در یک روز را با فرمت h:mm:ss چاپ کنید.
دقت کنید شما باید دقیقاً ۳ خط چاپ کنید. به ازای درست بودن هر کدوم از این خطوط نمره‌ی مشخص شده را دریافت خواهید کرد. تست‌های ۱ و ۲ و ۳ همان ورودی نمونه هستند و در هر کدام درست بودن همان خط بررسی میشود. تست‌های ۴ و ۵ و ۶ نیز به ترتیب مربوط به خطوط ۱ و ۲ و ۳ هستند. مثلاً اگر شما خط سوم خروجی‌تان درست باشد باید تست‌های ۳ و ۶ را درست جواب بدهید.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۰۲۴ مگابایت
----------
میکائیل جدیدا شغل شریف معلمی رو اختیار کرده و الان موقع تحویل برگه امتحانای دانش آموزا شده. دانش آموزها یک صف به طول $n$ جلوی میز میکائیل تشکیل دادن. از اونجا که ضعف تو ترج (شهری که میکائیل توش درس می‌ده) بیداد میکنه، نمره هر کسی نهایتا ۱۰ شده. وقتی برگه‌های تصحیح شده پخش بشه، هر نفر به هر کدوم از کناری‌هاش تو صف نگاه میکنه، اگه نمره‌ی اون از نمره خود بچه بیشتر شده بود، به اندازه اختلاف نمره‌هاشون ناراحت میشه. میکائیل قلب مهربونی داره. میخواد جمع ناراحتی‌های کل بچه‌های کلاسش حداکثر $k$ بشه. میکاییل میتونه هر مرحله برگه‌ی یک نفرو بگیره، یا یه نمره بهش ارفاق کنه یا اینکه الکی یه نمره ازش کم کنه. حالا چون میکائیل میخواد کسی شک بهش نکنه، میخواد با کمینه تعداد دستکاری تو برگه‌ها به هدفش برسه. طبق معمول اون زنگ زده به شما که کمکش کنید.
# ورودی
در خط اول ورودی، دو عدد $n$ و $k$ داده میشود.
در خط بعد، $n$ عدد داده میشود که عدد $a_i$ نشان‌دهنده‌ی نمره‌ی دانش‌آموز $i$ام است.
$$ 1 \le n \le 1\ 000$$
$$ 0 \le k \le 10 \times n$$
$$ 1 \le a_i \le 10$$
# خروجی
در تنها خط خروجی، کمترین تعداد مرحله‌ای که لازم هست تا میکائیل به هدفش برسد را چاپ کنید.
# مثال
## ورودی نمونه ۱
```
2 1
1 10
```
## خروجی نمونه ۱
```
8
```
## ورودی نمونه ۲
```
3 2
10 1 10
```
## خروجی نمونه ۲
```
8
```
درس زندگی
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۱۰۲۴ مگابایت
میکائیل جدیدا شغل شریف معلمی رو اختیار کرده و الان موقع تحویل برگه امتحانای دانش آموزا شده. دانش آموزها یک صف به طول n جلوی میز میکائیل تشکیل دادن. از اونجا که ضعف تو ترج (شهری که میکائیل توش درس می‌ده) بیداد میکنه، نمره هر کسی نهایتا ۱۰ شده. وقتی برگه‌های تصحیح شده پخش بشه، هر نفر به هر کدوم از کناری‌هاش تو صف نگاه میکنه، اگه نمره‌ی اون از نمره خود بچه بیشتر شده بود، به اندازه اختلاف نمره‌هاشون ناراحت میشه. میکائیل قلب مهربونی داره. میخواد جمع ناراحتی‌های کل بچه‌های کلاسش حداکثر k بشه. میکاییل میتونه هر مرحله برگه‌ی یک نفرو بگیره، یا یه نمره بهش ارفاق کنه یا اینکه الکی یه نمره ازش کم کنه. حالا چون میکائیل میخواد کسی شک بهش نکنه، میخواد با کمینه تعداد دستکاری تو برگه‌ها به هدفش برسه. طبق معمول اون زنگ زده به شما که کمکش کنید.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۰۲۴ مگابایت
------------------------------
**صورت سوال و ورودی‌ها در این سوال دقیقاً با ساعت‌کاری سبک برابر است. تنها تفاوت این دو سوال، خروجی‌ای‌ست که شما بایستی چاپ کنید**.
در شرکت کوئرا $n$ نفر مشغول به کارند که جز باقر (رئیس شرکت) هر نفر بالادستی‌ای دارد. به مجموعه‌ی هر فرد و زیردستانش و زیردستانِ زیردستانش و... تیم او می‌گوییم. مثلاً تیم باقر برابر کل اعضای شرکت است. در واقع ساختار شرکت شبیه یک **جنگل** (گراف جهت‌دار بدون دور) است.
این روزها کوئرا با $m$ پروژه‌ی سخت و نفس‌گیر دست و پنجه نرم می‌کند. اعضای کوئرا شدیدن مشغولند و وقت سر خاراندن‌شان نیست. هر پروژه تعدادی زیرپروژه دارد. به مجموعه‌ی هر پروژه و زیرپروژه‌هایش و زیرپروژه‌های زیرپروژه‌هایش و... پراجکت‌باکس آن پروژه می‌گوییم. در واقع ساختار پروژه‌ها شبیه یک **جنگل** (گراف جهت‌دار بدون دور) است.
سِپَسَک، سامانه‌ی پردازش ساعت‌های کاری، ایده‌ای بدیع از استاد باقر است که قرار است اثر چشم‌گیری در رشد و پیش‌رفت شرکت مذکور داشته باشد. داستان از این‌جا شروع میشود که شما باید این سیستم را بنویسید.
پس از گذشت چند سال از شروع به کار کوئرا هم اکنون اعضای خوش‌تلاش کوئرا همه‌ی پروژه‌ها را تحویل داده اند. باقر ساعت‌های کاری شرکت از بدو شروع به کار کوئرا را در ورودی به شما تحویل می‌دهد. شما باید در راستای تکمیل سپسک تحلیل‌هایی بر روی ساعت‌های کاری اعضای کوئرا انجام دهید.
# ورودی
در خط اول ورودی دو عدد $n$ و $m$ و $k$ آمده است که تعداد اعضای شرکت و تعداد پروژه‌ها و تعداد رکوردها را نشان می‌دهد.
در خط بعد $n-1$ عدد آمده‌ست که $i$امین آنها شماره‌ی بالادستی نفر $i+1$ام را نشان می‌دهد. دقت کنید شماره‌ی باقر ۱ می‌باشد و بالادستی ندارد.
در خط بعد $m$ عدد آمده‌ست که $i$امین آنها شماره‌ی پروژه‌ای که شامل پروژه‌ی $i$ام میشود را نشان می‌دهد. اگر پروژه‌ی دیگری شامل این پروژه نشود این عدد برابر صفر خواهد بود.
در خط بعد $m$ عدد آمده‌ست که $i$امین آنها سود پروژه‌ی $i$ام را نشان می‌دهد. دقت کنید سود هر پروژه مستقل از زیرپروژه‌های آن است.
در ادامه $k$ خط می‌آید که هر کدام یک رکورد ساعت‌کاری‌ست. هر رکورد به فرمت `YY/MM/DD hh:mm:ss Person Project Type` است که `Person` برابر شماره‌ی فرد است، `Project` شماره‌ی پروژه‌ست و `Type` برابر `Start` یا `End` است که نشان‌دهنده‌ی این است که این رکورد شروع یا پایان یک ساعت کاری را نشان می‌دهد.
$$1 \le n, m, k \le 300\ 000$$
شماره‌ی بالادستی هر نفر از خودش کوچکتر است.
شماره‌ی پروژه‌ی شامل‌شونده‌ی پروژه‌ی دیگر (در صورت وجود) از آن کوچکتر است.
کوئرا در سال ۹۴ تاسیس شد و تاریخ پیش از آن به شما داده نخواهد شد. همچنین تاریخی پس از سال ۹۸ نیز به شما داده نخواهد شد.
هر بازه‌ای از ساعت کاری که شروع شده است لزوماً تمام هم شده است و $k$ زوج است.
سود هیچ پروژه‌ای از ۱ میلیارد بیشتر نیست.
ممکن نیست یک نفر هم‌زمان در حال انجام چند کار باشد.
# خروجی
در خط اول $n$ عدد چاپ کنید که $i$امین آنها میزان کار انجام شده توسط تیم نفر $i$ است. این زمان‌ها را با فرمت `h:mm:ss` چاپ کنید (تعداد ارقام بخش ساعت اهمیتی ندارد، ولی اگر صفر باشد باید صفر را چاپ کنید، مثلاً اگر کسی ۱۳ دقیقه و ۱۷ ثانیه کار کرده باشد باید `0:13:17` چاپ کنید).
در خط بعد $m$ عدد چاپ کنید که $i$امین آنها میزان کار انجام شده بر روی پراجکت‌باکس $i$ است. این زمان‌ها را با فرمت `h:mm:ss` چاپ کنید.
در خط بعد بیشترین کار انجام شده توسط کل اعضای شرکت در بازه‌ای به طول ۲۴ ساعت را چاپ کنید.
در خط بعد سودی که هر شخص شرکت عاید شرکت کرده‌ست را به تومان چاپ کنید. سودی که یک نفر عاید شرکت کرده‌ست برابر جمع سود پروژه‌هایی‌ست که او انجام داده است. همچنین اگر شخصی بخشی از یک پروژه را انجام داده باشد به همان کسری از پروژه که انجام داده است به شرکت سود رسانده است. در واقع اگر این شخص مجموعاً $A$ ثانیه روی این پروژه کار کرده باشد و کل پروژه $T$ ثانیه وقت برده باشد و سود آن $S$ باشد این شخص
$\frac{A}{T} \times S$
سود عاید شرکت کرده است. برای مثال اگر فرد ۱۳۱ ثانیه روی پروژه‌ای که مجموعاً ۳۱۳ ثانیه وقت برده است و ۱۳ تومان سود برای کوئرا داشته است کار کرده باشد (و روی پروژه‌ی دیگری کار نکرده باشد) شما باید `5.440894` را چاپ کنید. اختلاف مطلق و نسبی شما با جواب درست نباید بیش از $10^{-4}$ باشد. در واقع اگر جواب شما $p$ و جواب درست $j$ باشد، در صورتی جواب شما درست در نظر گرفته میشود که
$\frac{|p - j|}{max(j, 1)} \le 10^{-4}$.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:-------:|:----------:|:-----------:|
|۱ | ۱۵ | تنها باید خط اول از خروجی شما صحیح باشد |
|۲| ۱۵ | تنها باید خط دوم از خروجی شما صحیح باشد |
|۳| ۳۰ | تنها باید خط سوم از خروجی شما صحیح باشد |
|۴| ۴۰ | تنها باید خط چهارم از خروجی شما صحیح باشد |
دقت کنید شما باید دقیقاً ۴ خط چاپ کنید. به ازای درست بودن هر کدوم از این خطوط نمره‌ی مشخص شده را دریافت خواهید کرد. تست‌های ۱ و ۲ و ۳ و ۴ همان ورودی نمونه هستند و در هر کدام درست بودن همان خط بررسی میشود. تست‌های ۵ و ۶ و ۷ و ۸ نیز به ترتیب مربوط به خطوط ۱ و ۲ و ۳ و ۴ هستند. مثلاً اگر شما خط سوم خروجی‌تان درست باشد باید تست‌های ۳ و ۷ را درست جواب بدهید.
# مثال
## ورودی نمونه
```
3 3 10
1 2
0 1 0
56 62 56
97/06/03 20:09:33 1 3 Start
97/06/03 20:19:57 3 2 Start
97/06/04 23:13:14 3 2 End
97/06/04 23:15:54 1 3 End
97/07/02 10:09:33 2 1 Start
97/07/02 10:15:54 2 1 End
97/07/03 23:09:33 1 2 Start
97/07/03 23:19:57 3 2 Start
97/07/04 01:13:14 3 2 End
97/07/04 01:15:54 1 2 End
```
## خروجی نمونه
```
58:05:37 28:52:55 28:46:34
30:59:16 30:52:55 27:06:21
48:00:00
60.227767 56.000000 57.772233
```
ساعت‌کاری سنگین
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۱۰۲۴ مگابایت
صورت سوال و ورودی‌ها در این سوال دقیقاً با ساعت‌کاری سبک برابر است. تنها تفاوت این دو سوال، خروجی‌ای‌ست که شما بایستی چاپ کنید.
در شرکت کوئرا n نفر مشغول به کارند که جز باقر (رئیس شرکت) هر نفر بالادستی‌ای دارد. به مجموعه‌ی هر فرد و زیردستانش و زیردستانِ زیردستانش و... تیم او می‌گوییم. مثلاً تیم باقر برابر کل اعضای شرکت است. در واقع ساختار شرکت شبیه یک جنگل (گراف جهت‌دار بدون دور) است.
این روزها کوئرا با m پروژه‌ی سخت و نفس‌گیر دست و پنجه نرم می‌کند. اعضای کوئرا شدیدن مشغولند و وقت سر خاراندن‌شان نیست. هر پروژه تعدادی زیرپروژه دارد. به مجموعه‌ی هر پروژه و زیرپروژه‌هایش و زیرپروژه‌های زیرپروژه‌هایش و... پراجکت‌باکس آن پروژه می‌گوییم. در واقع ساختار پروژه‌ها شبیه یک جنگل (گراف جهت‌دار بدون دور) است.
سِپَسَک، سامانه‌ی پردازش ساعت‌های کاری، ایده‌ای بدیع از استاد باقر است که قرار است اثر چشم‌گیری در رشد و پیش‌رفت شرکت مذکور داشته باشد. داستان از این‌جا شروع میشود که شما باید این سیستم را بنویسید.
پس از گذشت چند سال از شروع به کار کوئرا هم اکنون اعضای خوش‌تلاش کوئرا همه‌ی پروژه‌ها را تحویل داده اند. باقر ساعت‌های کاری شرکت از بدو شروع به کار کوئرا را در ورودی به شما تحویل می‌دهد. شما باید در راستای تکمیل سپسک تحلیل‌هایی بر روی ساعت‌های کاری اعضای کوئرا انجام دهید.
در خط اول ورودی دو عدد n و m و k آمده است که تعداد اعضای شرکت و تعداد پروژه‌ها و تعداد رکوردها را نشان می‌دهد.
در خط بعد n−1 عدد آمده‌ست که iامین آنها شماره‌ی بالادستی نفر i+1ام را نشان می‌دهد. دقت کنید شماره‌ی باقر ۱ می‌باشد و بالادستی ندارد.
در خط بعد m عدد آمده‌ست که iامین آنها شماره‌ی پروژه‌ای که شامل پروژه‌ی iام میشود را نشان می‌دهد. اگر پروژه‌ی دیگری شامل این پروژه نشود این عدد برابر صفر خواهد بود.
در خط بعد m عدد آمده‌ست که iامین آنها سود پروژه‌ی iام را نشان می‌دهد. دقت کنید سود هر پروژه مستقل از زیرپروژه‌های آن است.
در ادامه k خط می‌آید که هر کدام یک رکورد ساعت‌کاری‌ست. هر رکورد به فرمت YY/MM/DD hh:mm:ss Person Project Type است که Person برابر شماره‌ی فرد است، Project شماره‌ی پروژه‌ست و Type برابر Start یا End است که نشان‌دهنده‌ی این است که این رکورد شروع یا پایان یک ساعت کاری را نشان می‌دهد.
1≤n,m,k≤300000
شماره‌ی بالادستی هر نفر از خودش کوچکتر است.
شماره‌ی پروژه‌ی شامل‌شونده‌ی پروژه‌ی دیگر (در صورت وجود) از آن کوچکتر است.
کوئرا در سال ۹۴ تاسیس شد و تاریخ پیش از آن به شما داده نخواهد شد. همچنین تاریخی پس از سال ۹۸ نیز به شما داده نخواهد شد.
هر بازه‌ای از ساعت کاری که شروع شده است لزوماً تمام هم شده است و k زوج است.
سود هیچ پروژه‌ای از ۱ میلیارد بیشتر نیست.
ممکن نیست یک نفر هم‌زمان در حال انجام چند کار باشد.
در خط اول n عدد چاپ کنید که iامین آنها میزان کار انجام شده توسط تیم نفر i است. این زمان‌ها را با فرمت h:mm:ss چاپ کنید (تعداد ارقام بخش ساعت اهمیتی ندارد، ولی اگر صفر باشد باید صفر را چاپ کنید، مثلاً اگر کسی ۱۳ دقیقه و ۱۷ ثانیه کار کرده باشد باید 0:13:17 چاپ کنید).
در خط بعد m عدد چاپ کنید که iامین آنها میزان کار انجام شده بر روی پراجکت‌باکس i است. این زمان‌ها را با فرمت h:mm:ss چاپ کنید.
در خط بعد بیشترین کار انجام شده توسط کل اعضای شرکت در بازه‌ای به طول ۲۴ ساعت را چاپ کنید.
در خط بعد سودی که هر شخص شرکت عاید شرکت کرده‌ست را به تومان چاپ کنید. سودی که یک نفر عاید شرکت کرده‌ست برابر جمع سود پروژه‌هایی‌ست که او انجام داده است. همچنین اگر شخصی بخشی از یک پروژه را انجام داده باشد به همان کسری از پروژه که انجام داده است به شرکت سود رسانده است. در واقع اگر این شخص مجموعاً A ثانیه روی این پروژه کار کرده باشد و کل پروژه T ثانیه وقت برده باشد و سود آن S باشد این شخص
TA×S
سود عاید شرکت کرده است. برای مثال اگر فرد ۱۳۱ ثانیه روی پروژه‌ای که مجموعاً ۳۱۳ ثانیه وقت برده است و ۱۳ تومان سود برای کوئرا داشته است کار کرده باشد (و روی پروژه‌ی دیگری کار نکرده باشد) شما باید 5.440894 را چاپ کنید. اختلاف مطلق و نسبی شما با جواب درست نباید بیش از 10−4 باشد. در واقع اگر جواب شما p و جواب درست j باشد، در صورتی جواب شما درست در نظر گرفته میشود که
max(j,1)∣p−j∣≤10−4.
دقت کنید شما باید دقیقاً ۴ خط چاپ کنید. به ازای درست بودن هر کدوم از این خطوط نمره‌ی مشخص شده را دریافت خواهید کرد. تست‌های ۱ و ۲ و ۳ و ۴ همان ورودی نمونه هستند و در هر کدام درست بودن همان خط بررسی میشود. تست‌های ۵ و ۶ و ۷ و ۸ نیز به ترتیب مربوط به خطوط ۱ و ۲ و ۳ و ۴ هستند. مثلاً اگر شما خط سوم خروجی‌تان درست باشد باید تست‌های ۳ و ۷ را درست جواب بدهید.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۰۲۴ مگابایت
------------------------------
قصد تبلیغ در تعدادی سایت برای جذب کاربران را داریم. $n$ کاربر و $m$ سایت و $k$ نوع تبلیغ داریم. سایت شماره‌ی $i$ پنلی به طول $l_i$ برای تبلیغ دارد. طول تبلیغ $i$اُم $s_i$ است. هر کاربر تعدادی سایت را بازدید خواهد کرد. همچنین ما میزان احتمال کلیک کردن هر کاربر بر روی هر تبلیغ (در صورت مشاهده‌ی آن در یک سایت) را میدانیم. ما قرار است تبلیغ‌ها را در سایت‌ها بچینیم. هدف ما بیشینه کردن امیدریاضی تعداد کلیک‌های کاربران بر روی تبلیغ‌هاست. بدیهی‌ست یک کاربر روی یک تبلیغ حداکثر یک بار کلیک می‌کند.
توجه‌کنید که در این مساله به دنبال این نیستیم که کمینه امیدریاضی را به دست آوریم و برنامه شما هر چه قدر راه حل بهتری را پیشنهاد بدهد نمره بیشتری دریافت خواهیدکرد.
# ورودی
در خط اول ورودی $n$ و $m$ و $k$ آمده است.
در خط دوم $m$ عدد آمده است که $i$اُمین آنها $l_i$ است.
در خط سوم $k$ عدد آمده است که $i$اُمین آنها $s_i$ است.
در $i$امین خط از $n$ خط بعدی ابتدا $num_i$ آمده‌ست که تعداد سایت‌هایی‌ست که نفر $i$ام از آنها بازدید می‌کند. سپس در ادامه $num_i$ عدد می‌آید که شماره‌ی سایت‌هایی که نفر $i$ام از آنها بازدید می‌کند را نشان می‌دهد.
در $i$امین خط از $n$ خط بعدی $k$ عدد آمده‌است که $j$امین آنها احتمال کلیک کردن فرد $i$ام بر روی تبلیغ $j$ام است. این اعداد با دقت دقیقاً ۶ رقم اعشار داده می‌شوند.
$$1 \le n, m, k \le 500$$
$$1 \le num_i \le m$$
$$1 \le l_i, s_i \le 10^9$$
تضمین میشود یک کاربر حداکثر یک‌بار از هر سایت بازدید می‌کند.
# خروجی
در خروجی $k$ خط چاپ کنید که در خط $i$ام ابتدا $x_i$ بیاید که تعداد سایت‌هایی‌ست که تبلیغ $i$ام باید در آنها قرار بگیرد. سپس $x_i$ عدد چاپ کنید، شماره‌ی سایت‌هایی که باید تبلیغ $i$ام در آنها قرار بگیرد.
# مثال
## ورودی نمونه
```
3 3 3
4 10 2
10 9 4
2 2 3
2 1 2
1 3
0.735807 0.437574 0.041877
0.878751 0.535907 0.056048
0.412099 0.997380 0.834622
```
## خروجی نمونه
```
1 2
0
1 1
```
در این نمونه تبلیغ اول در سایت دوم و تبلیغ سوم در سایت اول نمایش داده میشود. تبلیغ دوم هم در هیچ سایتی قرار نمی‌گیرد.
تبلیغات
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۱۰۲۴ مگابایت
قصد تبلیغ در تعدادی سایت برای جذب کاربران را داریم. n کاربر و m سایت و k نوع تبلیغ داریم. سایت شماره‌ی i پنلی به طول li برای تبلیغ دارد. طول تبلیغ iاُم si است. هر کاربر تعدادی سایت را بازدید خواهد کرد. همچنین ما میزان احتمال کلیک کردن هر کاربر بر روی هر تبلیغ (در صورت مشاهده‌ی آن در یک سایت) را میدانیم. ما قرار است تبلیغ‌ها را در سایت‌ها بچینیم. هدف ما بیشینه کردن امیدریاضی تعداد کلیک‌های کاربران بر روی تبلیغ‌هاست. بدیهی‌ست یک کاربر روی یک تبلیغ حداکثر یک بار کلیک می‌کند.
توجه‌کنید که در این مساله به دنبال این نیستیم که کمینه امیدریاضی را به دست آوریم و برنامه شما هر چه قدر راه حل بهتری را پیشنهاد بدهد نمره بیشتری دریافت خواهیدکرد.
در iامین خط از n خط بعدی ابتدا numi آمده‌ست که تعداد سایت‌هایی‌ست که نفر iام از آنها بازدید می‌کند. سپس در ادامه numi عدد می‌آید که شماره‌ی سایت‌هایی که نفر iام از آنها بازدید می‌کند را نشان می‌دهد.
در iامین خط از n خط بعدی k عدد آمده‌است که jامین آنها احتمال کلیک کردن فرد iام بر روی تبلیغ jام است. این اعداد با دقت دقیقاً ۶ رقم اعشار داده می‌شوند.
1≤n,m,k≤5001≤numi≤m1≤li,si≤109
تضمین میشود یک کاربر حداکثر یک‌بار از هر سایت بازدید می‌کند.
در خروجی k خط چاپ کنید که در خط iام ابتدا xi بیاید که تعداد سایت‌هایی‌ست که تبلیغ iام باید در آنها قرار بگیرد. سپس xi عدد چاپ کنید، شماره‌ی سایت‌هایی که باید تبلیغ iام در آنها قرار بگیرد.