+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در نخستین دوره‌ی مسابقه‌ **گلدن کد**، برنامه‌نویس‌ها برای بدست آوردن بیشترین **میلی** (واحد طلای شرکت میلی معادل یک میلی گرم طلا) با یکدیگر رقابت می‌کنند. برگزارکنندگان برای هیجان بیشتر تصمیم گرفته‌اند بخشی از جایزه را به شکل خاصی بین شرکت‌کنندگان تقسیم کنند؛ به طوری که فقط نفرات برتر برنده نباشند، بلکه جمع بیشتری مشمول جوایز شوند. در این سیستم به جز جوایز اصلی، یک **معدن میلی** حاوی $M \times 2^M$ میلی وجود دارد که میان $2^K$ نفر اول جدول رتبه‌بندی تقسیم می‌شود (به $2^K$ نفر برتر مسابقه، میلی‌کاوان می‌گوییم.). میلی‌های این معدن به اندازه‌های برابر بین سوال‌هایی که حداقل یک میلی‌کاو آن را حل کرده باشد، به عنوان **میلی‌جایزه** آن سوال تقسیم می‌شود. سپس میلی‌جایزه هر سوال، به صورت مساوی بین تمام میلی‌کاوانی که این سوال را حل کرده باشند،تقسیم می‌شود. در پایان بعد از تقسیم میلی‌جایزه‌ها و اختصاص میلی‌‌ها به افراد و جمع میلی‌جایزه سوال های هر نفر، جایزه او رو به بالا گرد می‌شود تا کوچکترین واحد جایزه یک میلی‌ باشد. دقت کنید هر شرکت‌کننده فقط در صورتی جایزه دریافت می‌کند که در جدول جزو میلی‌کاوان باشد و همچنین حداقل یک سوال حل کرده باشد. # ورودی در سطر اول سه عدد $K$ ،$M$ ،$N$ به ترتیب داده می‌شود. که به ترتیب $N$ نشان‌دهنده تعداد شرکت کنندگان و $M$ پارامتر مربوط به حجم معدن میلی و $K$ پارامتر مربوط به تعداد میلی‌کاوان است. $$1 \le N \le 2^{15}$$ $$1 \le M \le 20$$ $$0 \le K \le 15$$ در ادامه $N$ سطر به عنوان اطلاعات شرکت‌کنندگان می‌آیند. هر سطر با رتبه‌ی یک شرکت‌کننده شروع می‌شود و سپس شماره سوالاتی که حل کرده است، داده می‌شود. تعداد سوالات مسابقه حداکثر $2^8$ است. # خروجی به ازای هر $N$ نفر مسابقه به همان ترتیبی که در ورودی آمده است، سهم میلی آن فرد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 5 1 3 1 2 4 5 1 1 4 7 4 2 ``` ## خروجی نمونه ۱ ``` 0 60 100 0 ``` با توجه به مقادیر، تعداد میلی‌کاوان 2 نفر و اندازه معدن میلی 160 می‌باشد. با توجه به اینکه نفر اول و دوم تنها سوالات 1 و 4 و 5 و 7 را حل کرده‌اند. میلی‌جایزه هر سوال 40 میلی است. کل میلی‌جایزه سوال 1 و 7 به نفر اول و کل میلی‌جایزه سوال 5 به نفر دوم می‌رسد. و میلی‌جایزه سوال 4 بین نفر اول و دوم تقسیم می‌شود. بنابراین سهم نفر اول 100 میلی‌ و سهم نفر دوم 60 میلی‌ است. ## ورودی نمونه ۲ ``` 10 10 3 5 1 3 6 1 1 1 2 3 5 8 2 2 3 5 7 8 4 1 3 5 10 9 3 1 5 6 7 8 7 2 ``` ## خروجی نمونه ۲ ``` 659 293 2244 2682 1024 0 0 2853 0 488 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- باربری طلا در شرکت میلی، توسط دو قطار سریع‌السیر مخصوص انجام می‌شود که ریل‌های آنها مانند دو خط صاف موازی، کنار یکدیگر قرار گرفته‌اند. تعدادی ایستگاه تخلیه بار بین این دو ریل و در امتداد ریل‌ها وجود که با نام‌های $0$ الی $X$ نام گذاری شده‌اند. هر ریل مخصوص یک قطار است و هر قطار همیشه بر روی ریل مربوط به خودش حرکت می‌کند. در ابتدا یک قطار در ایستگاه $0$ است و جهت حرکت آن به سمت ایستگاه $X$ است و دیگری در ایستگاه $X$ قرار دارد و جهت حرکت آن به سمت ایستگاه $0$ است. قطارها از ابتدا ثانیه $0$ شروع به حرکت می‌کنند. و در جهت حرکتشان هر ثانیه به اندازه فاصله بین دو ایستگاه، به جلو می‌روند (بعد از $X$ ثانیه به ایستگاه آخر در جهت حرکتشان می‌رسند). هر قطار بعد از رسیدن به ایستگاه آخر، بلافاصله و بدون از دست‌دادن زمان، جهت حرکتش را عوض می‌کند و در ریل قبلی خودش به سمت مخالف شروع به حرکت می‌کند. به دلیل قیمت بالا طلا، کارکنان شرکت میلی خودشان شخصا باربری طلاها را با قطار انجام می‌دهند. هر کارمند در زمان مشخصی (برای هر کارمند می‌تواند متفاوت یا تکراری باشد) با بسته‌ طلا در دستش وارد یکی از ایستگاه‌های $0$ یا $X$ می‌شود و می‌خواهد که سوار قطار شده و در ایستگاه مقصد مشخصی پیاده شود و بسته طلا را تحویل دهد. او در ایستگاه مبدا منتظر می‌ماند و هرگاه قطاری در آن ایستگاه در حال شروع حرکت باشد، سوار می‌شود و هنگام رسیدن قطار به ایستگاه مقصد، از قطار پیاده می‌شود. بسته را تحویل می‌دهد و سپس همانجا ناپدید می‌شود (به دلیل استرس زیاد از حمل طلا). **پیاده و سوار شدن مسافران هزینه زمانی ندارد**. می‌دانیم هر گاه این دو قطار از کنار هم عبور کنند، همه کارکنانی که در هر دو قطار هستند برای همه‌ی کارکنان قطار روبه‌رویی دست تکان می‌دهند (حتی آنهایی که می‌خواهند در همان نقطه از قطار پیاده شوند). هر فرد به اندازه تعداد نفراتی که برای آنها دست تکان داده است خوشحال می‌شود. خوشحالی شرکت میلی بعد از اتمام باربری، برابر است با مجموع خوشحالی کارکنان آن تقسیم بر دو (به ازای هر دو نفر یک واحد). پس شرکت میلی دوست دارد که مجموع خوشحالی را بیشینه کند. میلی به شما عدد $k$ را ورودی می‌دهد و از شما می‌خواهد حداکثر $k$ نفر از کارمندانی که ایستگاه مبدا آنها 0 است را انتخاب کنید و زمان رسیدن آنها به مبدا را طوری تغییر دهید که در نهایت خوشحالی بیشینه شود. این خوشحالی بیشینه را خروجی دهید. # ورودی ورودی شامل تعدادی سناریو مختلف است. در خط اول هر ورودی عدد $T$، تعداد سناریوها ورودی داده می‌شود. سپس در خط اول هر سناریو به ترتیب سه عدد $n$ و $X$ و $k$ داده می‌شود. سپس در خط $i$ام از هر کدام از $n$ خط بعدی، سه عدد $dir_i$ و $time_i$ و $pos_i$ داده می‌شود که نشان‌دهنده مبدا، زمان رسیدن به مبدا و ایستگاه مقصد کارمند $i$ام است. در صورتی که $dir_i$ برابر 0 باشد یعنی مبدا این کارمند ایستگاه 0 است. در غیر اینصورت برابر 1 است و یعنی ایستگاه $X$ مبدا این کارمند است. $$ \sum n \leq 2 \cdot 10^5 $$ $$ 0 \leq time_i, pos_i\leq 10^9 $$ $$ 1 \leq X \leq 10^9 $$ # خروجی برای هر سناریو، بیشینه خوشحالی را بعد از $k$ تغییر، در یک خط جداگانه چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 6 4 0 0 3 2 1 4 1 0 5 1 0 6 3 1 7 0 1 8 2 6 4 1 0 3 2 1 4 1 0 5 1 0 6 3 1 7 0 1 8 2 ``` ## خروجی نمونه ۱ ``` 3 4 ``` در نمونه‌ی اول، در زمان $6$ یک قطار حاوی شخص $1$ و یک قطار حاوی شخص $2$ به هم می‌رسند. در زمان $10$ یک قطار حاوی شخص $4$ و یک قطار حاوی شخص $5$ و $6$ به هم می‌رسند. در نمونه‌ی دوم، کافیست زمان شخص $1$ را به $5$ تغییر دهیم.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- + بخش تعریفی این سوال، قبل از *روش جهتدهی راهروها* با سوال **سالن‌های ذخیره طلا در شرایط حساستر** یکسان است. اما هدف سوال متفاوت است. نقشه سالن‌های ذخایر طلای میلی به ما داده شده است. $n$ سالن داریم و این سالن‌ها با $n-1$ راهرو به هم متصل شده‌اند و از تمام سالن‌ها به همه سالن‌ها می‌توان رسید (مانند یک درخت در دنیای گراف‌ها). از آنجا که امنیت برای ما خیلی مهم است نمی‌خواهیم دسترسی سالن‌ها به یکدیگر زیاد باشد. به همین منظور، می‌خواهیم راهروها را یک طرفه کنیم به شکلی که فقط از یک سالن در یک طرف راهرو بتوان به سالن دیگر رفت و برعکس آن امکان پذیر نباشد. بعد از یک طرفه کردن راهروها، ضعف نقشه را تعریف می‌کنیم تعداد جفت مرتب سالن‌هایی که به هم مسیر دارند (می‌توان از سالن اول با استفاده از راهروها در جهت تایین شده به سالن دوم رسید). به شما نقشه اولیه سالن‌ها و راهروها داده شده است و شما باید راهروها را طوری جهت‌دهی کنید که نقشه در نهایت کمینه ضعف را داشته باشد. # ورودی ورودی شامل دو خط است. در خط اول ورودی تعداد سالن‌های ذخایر طلای میلی $n$، می‌آید. می‌دانیم نقشه سالن‌ها یک درخت است که راس‌های آن سالن‌ها هستند یال‌های این درخت نیز راهروها هستند. درخت مفروض را از راس منتصب به سالن $1$ ریشه‌دار کرده‌ایم. این درخت ریشه‌دار شده در خط دوم ورودی، به شما ورودی داده می‌شود. در خط دوم ورودی $n-1$ عدد متوالی به شکل $par_2, par_3, \ldots, par_n \ $ می‌آید که $par_i$ نشان‌دهنده پدر راس منتصب به سالن $i$، در درخت ریشه‌دار شده است. این به این معنی است که بین سالن $i$ و و سالن $par_i$ یک راهرو وجود دارد. # محدودیت‌ها $$ 1 \le n \le 2 \times 10^5 $$ $$ 1 \le par_i < i $$ # خروجی در خط اول خروجی کمینه ضعف را خروجی دهید. سپس در خط دوم خروجی یک رشته شامل $n-1$ کاراکتر خروجی دهید که کاراکتر $i$ ام نشان‌دهنده‌ی جهت یال بین راس منتصب به سالن$i+1$ ام و پدرش است. اگر این کاراکتر `U` باشد یعنی این یال از خودش به سمت پدرش جهت دار شده است، و اگر `D` باشد یعنی این یال از سمت پدرش به سمت خودش جهت دار شده است. اگر چند جواب با کمینه تاریکی وجود داشت، رشته‌ای را خروجی دهید که لکسیکوگرافیکالی کمینه باشد. # مثال ## ورودی نمونه ۱ ``` 3 1 2 ``` ## خروجی نمونه ۱ ``` 2 DU ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ----- دور میز دایره‌ای ناهار در شرکت میلی تعدادی کیسه شامل سکه‌ طلا داریم. این کیسه‌ها ممکن است حاوی تعدادی سکه طلا و تعدادی سکه تقلبی باشند. هر کیسه یک عدد به عنوان ارزش دارد که تعداد سکه‌های طلا آن را نشان میدهد. به دلیل اینکه طلا از اهمیت زیادی برای این شرکت برخوردار است، در صورتی که کیسه‌ای حاوی سکه‌ قلابی باشد به ازای هر سکه قلابی یک ارزش منفی می‌گیرد. پس ارزش هر کیسه برابر است با تعداد سکه‌های طلا آن منهای تعداد سکه‌های قلابی آن. میلی برای آشمز یک چالش تعریف کرده که آیا می‌تواند با تکرار یک عملیات روی میز، ارزش تمام کیسه‌ها را صفر کند؟ او در هر عملیات می‌تواند یک کیسه انتخاب کند و داخل آن یک سکه تقلبی بیندازد و در کیسه بعدی (در جهت عقربه‌های ساعت) یک سکه طلا بیندازد. او از شما می‌خواهد کمترین تعداد عملیات را محاسبه کنید تا بتواند ارزش تمام کیسه‌ها را صفر کند. تضمین می‌شود که همه تست کیس ها راه حل دارند. # ورودی در خط اول ورودی تعداد تست‌کیس ها $T$ می‌آید. در خط اول هر تست‌کیس عدد $n$ ، تعداد کیسه‌ها می‌آید. در خط دوم هر تست‌کیس، از یکی از کیسه‌ها شروع می‌کنیم و به ترتیب در جهت عقربه‌های ساعت ارزش کیسه‌ها ورودی داده می‌شود (کیسه بعد از آخرین کیسه، همان اولین کیسه است). $a_1, a_2, \ldots, a_n$ $$1 \le T \le 10^4$$ $$1 \le n \le 2 \times 10^5$$ $$-10^9 \le a_i \le 10^9$$ تضمین می‌شود جمع تعداد کیسه‌ها در همه تست‌کیس‌ها حداکثر $2 \times 10^5$ می‌باشد. # خروجی جواب هر تست‌کیس را در یک خط جداگانه خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 2 2 -2 4 4 0 -2 -2 5 1 0 -2 3 -2 ``` ## خروجی نمونه ۱ ``` 2 10 8 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از خداحافظی کِشی و سفر او به جزایر ایبیزا برای گذراندن دوران بازنشستگی خود و خرج کردن میلی‌های بدست آمده از مسابقه، آشمَز و صَفَر تصمیم گرفتند به یاد دوران خوشی که با هم گذراندند صندلی او را بازنشسته کنند. آن‌ها با این تغییر بزرگ نیاز به یک استراتژی جدید دارند. با توجه به هماهنگی بالای این تیم سربار جا‌به‌جا کردن کیبورد از سربار انتقال راه‌حل بیشتر است. پس آن‌ها تصمیم می‌گیرند که بخش حل سوال و پیاده‌سازی راه‌حل را بین خود تقسیم کنند. به این صورت که صفر سوال‌ها را حل می‌کند و دست به کیبورد نمی‌برد و آشمز دائما پشت کیبورد است و حتی صورت سوال‌ها را نمی‌خواند. صفر بعد از حل هر سوال راه‌حل آن را به آشمز انتقال می‌دهد و آشمز بلافاصله شروع به پیاده‌سازی آن می‌کند (انتقال راه‌حل زمانی نمی‌گیرد). اما کشی هنوز دلسوز تیم است و دورادور عملکرد آن‌ها را بررسی می‌کند. صفر و آشمز در یک ماراتون استقامت شرکت کرده‌اند. این ماراتون $n$ سوال دارد. کشی که به خوبی به مهارت‌های بچه‌ها آشناست می‌داند حل سوال $i$-ام دقیقا $a_i$ ثانیه از صفر وقت می‌گیرد و همچنین پیاده‌سازی آن دقیقا $b_i$ ثانیه از آشمز وقت می‌گیرد. آن‌ها تا فول کردن کانتست ادامه خواهند داد. از آنجایی که استراتژی ترتیب حل سوالات از مهم‌ترین عوامل موثر بر عملکرد است، کشی قصد دارد بهترین استراتژی ممکن را پیدا کند. اما از آنجا که او بازنشسته شده و در همین حین در سواحل در حال آفتاب گرفتن و نوشیدن یک لیوان پیناکولادا با دو نی هستند (که به جای لیوان در یک پوست نارگیل سرو می‌شود)، از شما می‌خواهد تا کمترین زمان لازم برای حل و پیاده‌سازی تمام سوالات را محاسبه کنید. # ورودی در خط اول ورودی عدد $t$،‌ تعداد تست‌کیس‌ها آمده است. سپس از خط بعدی تست‌کیس‌ها ورودی داده می‌شوند. در خط اول هر تست‌کیس، عدد $n$ آمده است. و در هر کدام از $n$ خط بعدی، در خط $i$امین خط، دو عدد $a_i$ و $b_i$ آمده‌اند. # خروجی برای هر تست‌کیس در یک خط جداگانه کمترین زمان لازم برای فول کردن کانتست را چاپ کنید. # محدودیت‌ها $$ 1 \leq t \leq 10^5 $$ $$ 1 \leq n \leq 4 \cdot 10^5 $$ $$ 1 \leq a_i, b_i \leq 10^6 $$ $$ \sum n \leq 4 \cdot 10^5 $$ # مثال ## ورودی نمونه ۱ ``` 2 3 2 1 1 1 1 3 6 6 4 7 3 3 5 7 4 5 6 7 6 ```` ## خروجی نمونه ۱ ``` 6 38 ```` در تست‌کیس اول کافیست ابتدا سوال سوم، سپس سوال دوم و در آخر سوال اول را حل کنند تا در ۶ ثانیه کانتست رو فول کنن.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- + بخش تعریفی این سوال، تا *جهت‌دهی اولییه راهروها* با سوال **سالن‌های ذخیره طلا** یکسان است. اما این دو سوال متفاوت‌اند. نقشه سالن‌های ذخایر طلای میلی به ما داده شده است. $n$ سالن داریم و این سالن‌ها با $n-1$ راهرو به هم متصل شده‌اند و از تمام سالن‌ها به همه سالن‌ها می‌توان رسید (مانند یک درخت در دنیای گراف‌ها). از آنجا که امنیت برای ما خیلی مهم است نمی‌خواهیم دسترسی سالن‌ها به یکدیگر زیاد باشد. به همین منظور، می‌خواهیم راهروها را یک طرفه کنیم به شکلی که فقط از یک سالن در یک طرف راهرو بتوان به سالن دیگر رفت و برعکس آن امکان پذیر نباشد. بعد از یک طرفه کردن راهروها، **عدد ضعف هر سالن را تعریف می‌کنیم، تعداد سالن‌هایی که می‌توان با استفاده از راهروها در جهت تایین شده، به آنها رسید**. رومینا برای بازپرسی آمده است و عدد ضعف سالن‌ها را روی یک کاغذ نوشته است. او به اندازه بیشترین اختلاف بین دو عدد از اعداد نوشته شده، تعجب می‌کند و نقشه را ناهمسان می‌خواند. خود شرکت میلی بعضی راهروها را جهت‌دهی کرده است و جهت این راهروها قابل تغییر نیست. شما باید بقییه راهروها را طوری جهت‌دهی کنید که نقشه در کمینه تعجب رومینا را به همراه داشته باشد. # ورودی در خط اول ورودی تعداد تست‌کیس ها $T$ می‌آید. ورودی هر تست‌کیس شامل دو خط است. در خط اول ورودی تعداد سالن‌های ذخایر طلای میلی $n$، می‌آید. می‌دانیم نقشه سالن‌ها در هر تست کیس یک درخت است که راس‌های آن سالن‌ها هستند یال‌های این درخت نیز راهروها هستند. درخت مفروض را از راس منتصب به سالن $1$ ریشه‌دار کرده‌ایم. این درخت ریشه‌دار شده در خط دوم ورودی، به شما ورودی داده می‌شود. در $n-1$ خط بعدی هر تست کیس اطلاعات یال‌ها داده می‌شوند. در $i$ امین خط ($2 \le i \le n$)، به ترتیب عدد $par_i$ و سپس کاراکتر $c_i$ می‌آید. که نشان‌دهنده پدر راس منتصب به سالن $i$ است. یعنی بین سالنهای $par_i$ و $i$ یک راهرو وجود دارد و به طور متناظر بین این دو راس نیز در درخت یال کشیده شده است. اگر $c_i$ برابر`D` باشد، جهت این یال از پدر به سمت $i+1$ است و اگر `U` باشد،جهت این یال از $i$ به سمت $par_i$ است و نهایتا اگر برابر `?` باشد، جهت آن نامعلوم است و شما باید آن را جهت‌دهی کنید. $$1 \le n \le 500$$ $$1 \le par_i < i$$ $$c_i \in \{ U, D, ? \}$$ تضمین می‌شود جمع $n$ های هر تست حداکثر $500$ باشد. # خروجی به ازای هر تست‌کیس، کمیته تعجب ممکن رومینا رابعد از جهت‌دهی سالن‌های ذخیره طلا در تنها یک خط خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 2 3 1 ? 1 ? 5 1 D 1 ? 2 D 2 ? ``` ## خروجی نمونه ۱ ``` 1 3 ```