+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- چند روز پیش بود که مشکلات اقتصادی گریبان‌گیر مربّاها هم شد. مربّاها که موجودات مهربونی هستند، تصمیم گرفتند که دنبال راه حل بگردند. پس یک جلسه تشکیل دادند و در جلسه این موضوع را بررسی کردند. مربّاها در نهایت به این نتیجه رسیدند که اصلی‌ترین نیاز آن‌ها شیشه است. مربّاها به محض این که متوجه این موضوع شدند تصمیم گرفتند که مصرف شیشه‌شان را تا جای ممکن پایین بیاورند، اما مشکل اصلی این است که وقتی مربّاها شیشه‌هایشان را می‌بینند هول می‌شوند و هر کدام به صورت تصادفی یک شیشه را که هنوز برایش جا دارد را انتخاب می‌کند و وارد همان شیشه می‌شود. به محض این که یک شیشه پر شود یا هیچ‌ مربّایی بدون شیشه نمانده باشد، در شیشه بسته می‌شود. اگر بعد از بسته شدن در همه‌ی شیشه‌ها مربّایی بیرون مانده باشد، آن مربّا از صمیم قلب ناراحت می‌شود.مربّاها هم چون همان‌طور که گفتیم موجودات مهربونی هستند، نمی‌خواهند که هیچ‌ مربّایی ناراحت شود. در ابتدا در شیشه $i$ ام، $a_i$ تا مربّا قرار دارد. شما باید به مربّاها کمک کنید که تا جای ممکن در مصرف شیشه صرفه‌جویی کنند. برای این کار شما می‌توانید وارد اتاق مربّاها بشوید وبه آن‌ها بگویید که تعدادی شیشه را داخل کمد بگذارند که در روز مبادا بتوانند از شیشه‌ها استفاده کنند. مقداری که شما به مربّاها می‌گویید باید بیش‌ترین مقداری باشد که هیچ مربّایی ناراحت نشود. # ورودی در خط اول ورودی به ترتیب $n$ که نشان دهنده تعداد شیشه‌های مربّای داخل اتاق و $k$ که نشان دهنده ظرفیت هر شیشه است، داده می‌شود. در خط دوم ورودی $n$ عدد داده می‌شود که عدد $i$ ام، $a_i$ است که نشان دهنده مقدار مربّایی است که وقتی وارد اتاق می‌شوید، در شیشه‌ی $i$ ام هست. $$1 \leq n \leq 100$$ $$1 \leq k \leq 100$$ همچنین در هیچ شیشه‌ای در ورودی، بیش از ظرفیتش مربّا نیست. # خروجی در تنها خط خروجی، بیشینه تعداد شیشه‌ای را که مربّاها می‌توانند بدون ناراحت شدن کنار بگذارند را پیدا کنید. # مثال ### ورودی نمونه ۱ ``` 5 4 3 4 1 2 2 ``` ### خروجی نمونه ۱ ``` 2 ``` مربّاها می‌توانند در ۳ شیشه جا شوند، پس می‌توانند ۲ شیشه را داخل کمد بگذارند. ### ورودی نمونه ۲ ``` 3 8 8 8 8 ``` ### خروجی نمونه ۲ ``` 0 ``` چون همه شیشه مربّا ها پر هستند، نمی توانیم شیشه ای را کنار بگذاریم. پس پاسخ برابر صفر می باشد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حالا که مربّاها در شیشه قرار گرفته‌اند، قرار شده که آن‌ها را در قفسه قرار دهند که مرتب باشند، چون مربّاها نظم و ترتیب را خیلی دوست دارند. مربّاها از طرفداران پر و پا قرص مد هم هستند؛ برای همین از یک طراح داخلی خواسته‌اند که یک قفسه‌بندی برای آن‌ها درست کند. طراح‌های داخلی‌ای که مربّاها می‌توانند از آن‌ها استفاده کنند، همگی شیاد هستند و ممکن است که دروغ بگویند. برای مربّاها خیلی مهم است که تعداد قفسه‌های قفسه‌بندی‌ای که از آن استفاده می‌کنند چه‌قدر است. چون قد مربّاها خیلی کوتاه است، مجبورند که قفسه‌ها را به جای دیوار، روی زمین بگذارند و به همین دلیل می‌توانند از قفسه‌هایی که پایین ندارند هم استفاده کنند. طرحی که به مربّاها ارائه شده از $n$ خط تشکیل شده. مربّاها خط $i$ام قفسه‌بندی را با دو مقدار $a_i$ و $b_i$ نشان می‌دهند که $a_i$ نشان دهنده شیب خط و $b_i$ نشان‌دهنده‌ی عرض از مبدا خط $i$ام روی جدول مختصات فرضی مربّاها است. از آن‌جایی که مربّاها به طراح‌های داخلی اعتماد ندارند، از شما خواسته‌اند که به آن‌ها بگویید که چند مربّا می‌توانند در قفسه‌بندی پیشنهادشده جا دهند. دقت کنید که اندازه‌ی شیشه‌های مربّا خیلی کوچک است و می‌توان آن‌ها را در قفسه‌های خیلی کوچک هم جای داد. # ورودی در خط اول ورودی، $n$ که نشان دهنده تعداد خطوط است، می‌آید. پس از آن در خط $i+1$ ام ورودی، به ترتیب دو عدد $a_i$ و $b_i$ می‌آیند که به ترتیب نشان دهنده شیب و عرض از مبدا خط $i$ ام می باشند. $$1 \leq n \leq 1\ 000$$ $$-10^9 \leq a_i, b_i \leq 10^9$$ # خروجی در تنها خط خروجی تعداد قفسه‌های قفسه‌بندی پیشنهاد شده را خروجی دهید. # مثال ### ورودی نمونه ۱ ``` 4 0 0 0 1 2 -1 -2 6 ``` ### خروجی نمونه ۱ ``` 10 ``` قفسه‌بندی پیشنهاد شده به شکل زیر می‌باشد. 

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از انقلاب صنعتی، مربّاها در کارخانه‌های ویژه‌ای که توسط انسان‌ها اداره می‌شود، تولید می‌شوند. در این کارخانه‌ها مراتب اداری از هر چیز دیگری مهم‌تر است. مراتب اداری در این کارخانه‌ها به این صورت است که آقای شماره‌ی ۱، رییس کارخانه است و همه‌ی کارهای کارخانه زیر نظر او انجام می‌گیرد. پس از رییس کارخانه، کارگران رتبه‌ی اول قرار دارند که همگی تحت فرمان مستقیم رییس کارخانه هستند. همچنین به ازای هر $i > 1$، هر کارگر رتبه‌ی $i$ام تحت فرمان مستقیم دقیقا یکی از کارگرهای رتبه‌ی $i-1$ هستند. بعلاوه، اگر انسان $x$ تحت فرمان انسان $y$ باشد و انسان $y$ تحت فرمان انسان $z$ باشد، انسان $x$ تحت فرمان انسان $z$ هم هست و هیچ‌کس دیگری در هیچ‌حالتی (به جز دو حالت تحت فرمان مستقیم و با واسطه که گفته شدند) تحت فرمان کس دیگری نیست. این سلسله مراتب سخت اداری، برای جلوگیری از فساد به وجود آمده؛ بدین صورت که اگر یک روز $i$ نفر از افراد تحت‌فرمان مستقیم انسان $x$ فساد کنند، انسان $x$ علاوه بر پرداخت جریمه‌ی فساد آن‌ها، باید به تعداد کسانی که به هر ترتیبی تحت فرمان او بودند و ملزم به پرداخت جریمه شده‌اند هم شیشه بپردازد (شیشه واحد پولی مربّاهاست که از قضا بسیار ارزشمند هم هست). همچنین او یک شیشه‌ هم برای تنبیه خودش باید بپردازد. به مجموع هزینه‌ای که انسان $x$ ملزم به پرداخت آن می‌شود، جریمه‌ی انسان $x$ می‌گوییم. در یکی از روزهای گرم و آفتابی تابستان، تمام کسانی که کسی تحت فرمان آن‌ها نبود، فساد کردند و ملزم به پرداخت جریمه‌ی $1$شیشه‌ای شدند. امروز جریمه‌ای که رییس باید بپردازد به دستش رسیده. او از مقدار هزینه‌ای که باید بپردازد ناراضی است، به همین دلیل، از شما خواسته هزینه‌ای که او باید بپردازد را تایید کنید. # ورودی در خط اول ورودی $n$ تعداد افراد کارخانه می‌آید. در خط دوم ورودی $n - 1$ عدد می‌آید که عدد $i$ ام، $p_i$ است که نشان می‌دهد که انسان $i+1$ تحت فرمان مستقیم انسان $p_i$ می‌باشد. $$1 \leq n \leq 100\ 000$$ $$1 \leq p_i \leq n$$ تضمین می‌شود که همه‌ی انسان‌ها تحت فرمان رییس کارخانه هستند. # خروجی در تنها خط خروجی تعداد هزینه‌ای که رییس باید بابت جریمه بپردازد را خروجی دهید. # مثال ### ورودی نمونه ۱ ``` 5 1 2 1 3 ``` ### خروجی نمونه ۱ ``` 12 ``` مقدار هزینه‌ای که هر شخص باید بکند به همراه سلسه مراتب کارخانه، به شکل زیر می‌باشد. 

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دیوان عدالت مربّا (MJC)، پروتکل جدید عدالت اداری خود در خصوص مبارزه با مفسدین اقتصادی را به مجلس ارائه کرده تا مورد تایید آلبالوها قرار بگیرد. در این پروتکل، دو لیست وجود دارد که در یکی از آن ها حداقل میزان اختلاس از بخش های مختلف دولت مربّا که منجر به مجازات «شیره‌کشی» خواهند شد آمده است. مثلا برای شیره‌کشی از یک مربای نگون بخت که از اداره‌ی سوم دولتی اختلاس کرده، نیاز به اثبات اختلاس «دقیقا» ۳ شیشه‌ای داریم (شیشه واحد پول مربّا‌هاست). مجلس مربّا پس از تایید این پروتکل و دادن جنبه قانونی به آن، در اولین اقدام، قصد دارد کپکی را که از دولت مربّا اختلاس کرده، شیره‌کشی کند تا عبرتی برای کپک‌ها باشد و از دشمنی با مربّاها دست بردارند. از این رو مجلس لیست ساختگی اختلاس‌های کپک را از هر بخش به MJC تحویل داده است، در این لیست ذکر «نشده» که کپک از کدام اداره مقدار $i$ام را اختلاس کرده و فقط گفته شده که کپک از ادارات اول تا $n$ام اختلاس کرده. کپک متهم با استفاده از دوستانش به این لیست دسترسی پیدا کرده و مقادیر آن را تغییر داده است، پس ممکن است این لیست برای شیره‌کش کردن کافی نباشد و لیست نیازمند تصحیح باشد. دیوان می‌تواند در هر مرحله، مقدار یکی از اختلاس‌ها را دوبرابر و یا دوبرابر بعلاوه یک کند و آن را با مقدار شیشه‌های لازم برای شیره‌کشی کردن از ادارات انطباق دهد. دیوان برای این کار از مربّاهای زبده‌ی خود استفاده می‌کند. این مربّاها در صورتی که بتوانند لیست اختلاس را تصحیح کنند، پس از مدتی به جواب می‌رسند و می‌توانند کپک را به سزای اعمال خود برسانند، اما اگر نتوانند متوجه این موضوع نمی‌شوند و سال‌ها به تلاش برای رسیدن به لیست درست می‌پردازند. دیوان از بابت این که مربّاهای زبده‌ی خود را برای مدتی از دست دهد و در نهایت هم نتواند اثبات کند که کپک، گناهکار است، نگران است. به همین دلیل دیوان از شما خواسته تا با مشاهده‌ی لیست اختلاس‌های تصحیح شده و لیست واقعی اختلاس‌ها، بگویید که آیا مربّاهای زبده‌ی دیوان می‌توانند اتهام کپک را ثابت کنند یا نه. برای فهم بهتر سوال، مثال را مشاهده کنید. # ورودی در خط اول ورودی عدد $n$ داده شده است که تعداد اداراتی که از آن‌ها اختلاس شده را نشان می‌دهد در خط دوم ورودی $n$ عدد می‌آید که عدد $i$ ام، $a_i$ است که میزان اختلاس از اداره‌ی $i$ام برای شیره‌کشی از کپک را نشان می‌دهد. در خط سوم ورودی $n$ عدد می‌آید که عدد $i$ ام، $b_i$ است که عدد $i$ام لیست دست‌کاری شده توسط کپک‌ها را نشان می‌دهد. $$1 \leq n \leq 100\ 000$$ $$1 \leq a_i, b_i \leq 10^9$$ توجه کنید که در لیست دست‌کاری شده، ترتیب مقادیر لزوما درست نیست. # خروجی در صورتی که مربّاها می‌توانستند لیست را اصلاح کنند، "YES" و در غیر این‌صورت عبارت "NO" را چاپ کنید. # مثال ### ورودی نمونه ۱ ``` 6 63 41 80 46 34 32 23 16 17 31 20 20 ``` ### خروجی نمونه ۱ ``` YES ``` یکی از مقادیر 20 به 80 و دیگری به 41 تغییر پیدا می‌کند. مقدار 31 به 63 تغییر پیدا می‌کند. مقدار 17 به 34، 16 به 32 و 23 به 46 تغییر پیدا می‌کند.

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مربّاها تازه با گراف آشنا شده‌اند و از قضا، خیلی هم از گراف خوششان آمده. به خاطر همین مربّاها تصمیم گرفتند یک جشن برای گراف‌ها برگزار کنند. مربّاها که آشنایی چندانی با گراف نداشتند، جشن را با یک گراف کوچک و جمع و جور شروع کردند. در واقع مربّاها جشن‌شان را با یک گراف دو راسی برچسب‌دار ساده شروع کردند که تنها یال آن راس شماره‌ی یک را به راس شماره‌ی دو وصل می‌کرد. قرار بود که در روز جشن هر کدام از مربّاها به همراه یک راس برچسب‌دار به جشن بیاید و یکی از یال‌های گراف را که تا حالا نوچ نشده، انتخاب کند و آن را نوچ کند، پس از آن هم راس برچسب‌دار خود را با استفاده از دو یال تمیز به دو سر یالی که نوچ کرده، وصل کند. اما شب قبل از جشن یکی از عسل‌ها که چشم دیدن جشن مربّاها را نداشت، برچسب‌هایی را که مربّاها در اختیار داشتند دزدید. صبح که مربّاها از خواب بیدار شدند دیدند که هیچ‌کدام از راس‌هایشان برچسب ندارد. همه‌ی مربّاها از فرط ناراحتی شربت گریه می‌کردند. بزرگ مربّاها که این وضع را دید، رفت و از داخل گاوصندوقش دو برچسب پیدا کرد و این دو برچسب را به دو راس گراف اولیه چسباند. مربّاها هم از این که این اتفاق افتاد کلی خوشحال شدند. بعد از این که همه‌ی مربّاها راس بدون برچسب خودشان را به گراف چسباندند، بزرگ مربّاها آن‌ها را دور هم جمع کرد و معمایی را برای آن‌ها مطرح کرد. بزرگ مربّاها ابتدا معنی بیشینه‌ شار (max flow) را در گراف برای مربّاها توضیح داد و سپس از آن‌ها خواست که بگویند در تمام حالات برگزاری جشن توسط مربّاها چند گراف با بیشینه شار حداقل $m$ از راس ۱ به راس ۲ تولید می‌شد. دو حالت برگزاری جشن متفاوتند اگر و فقط اگر گراف ساخته شده در پایان این دو جشن متفاوت باشد، در واقع ترتیب انتخاب یال‌ها مهم نیست. دقت کنید، راس‌های افزوده شده برچسب ندارند (ولی راس ۱ و ۲ دارند). مربّاها که تازه با گراف آشنا شده بودند نتوانستند که این معما را حل کنند، به همین دلیل پیش شما آمدند تا جواب این معما را به آن‌ها بگویید و مربّاها شرمنده‌ی بزرگشان نشوند. البته آن‌ها متوجه این موضوع هستند که برای شما کار با اعداد خیلی بزرگ سخت است، به همین دلیل باقیمانده‌ی پاسخ معما را بر $10^9 + 7$ هم بگویید، مربّاها از شما متشکر خواهند شد. پی‌نوشت: می‌توانید از [اینجا](https://fa.wikipedia.org/wiki/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%A8%DB%8C%D8%B4%DB%8C%D9%86%D9%87_%D8%AC%D8%B1%DB%8C%D8%A7%D9%86#%D8%AA%D8%B9%D8%B1%DB%8C%D9%81) اطلاعات بیش‌تری درباره‌ی بیشینه شار به دست بیاورید. # ورودی در تنها خط ورودی، $n$ و $m$ می آیند که به ترتیب نشان دهنده تعداد مربّا و حداقل میزان بیشینه شار می باشند. $$1 \leq n, m \leq 10\ 000$$ # خروجی در تنها خط خروجی باقیمانده‌ی پاسخ معما بر $10^9 + 7$ را چاپ کنید. # مثال ### ورودی نمونه ۱ ``` 2 2 ``` ### خروجی نمونه ۱ ``` 2 ``` مربّای اول مجبور است تنها یال گراف را انتخاب کند. و نفر دوم هر یک از دو یال جدید را می‌تواند انتخاب کند. در هر دوی این حالات بیشینه شار برابر ۲ است.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مربّاها که از حل معما خوششان آمده بود، از بزرگشان خواستند که معمای دیگری به آن‌ها بگوید. بزرگ مربّاها پس از کمی فکر این معما را برای مربّاها مطرح کرد: یک مثلث قائم‌الزاویه $n \times n$ داریم. مثلث از $n$ ستون تشکیل شده که ستون $i$ام آن، $n - i$ سطر دارد. در $m$ تا از خانه‌های مثلث مربّا و در بقیه خانه‌های آن عسل قرار داده شده است. یک زیرمثلث $k$تایی نشان‌گر اشتراک خانه‌های $k$ سطر و $k$ ستون متناظر آن‌ها از مثلث است. یک زیرمثلث خوب، زیرمثلثی‌است که در تمام خانه‌های آن مربّا قرار دارد. همچنین زیرمثلث دوست‌داشتنی زیر‌مثلثی‌است که به ازای هر سطر آن، در اجتماع خانه‌های آن سطر و ستون متناظرش دو مربّا وجود داشته باشد. علاوه بر این یک زیرمثلث عجیب، زیرمثلثی‌ است که دوست‌داشتنی باشد، ولی هیچ زیرمثلثی از آن دوست‌داشتنی نباشد. تعداد زیرمثلث‌های $k$تایی خوب مثلث برابر با $f(k)$ است. بزرگ مربّاها از آن‌ها خواست تا مقدار $$\Sigma_{i = 1}^n f(i) \times (-1)^{i+1}$$ را بیابند. مربّاها که از شنیدن این معما گیج شده بودند، از بزرگ مربّاها خواستند تا کمکی به آن‌ها بکند. بزرگ مربّاها کمی فکر کرد و سپس به مربّاها گفت که کاری می‌کند که اگر زیرمثلث $k$تایی عجیب در مثلث بود، $k \leq 3$ باشد. مربّاها بعد از این که بزرگشان این شرط را روی مثلث گذاشت، باز هم نتوانستند مسئله را حل کنند، برای همین باز هم دست به دامن شما شدند. لطفا به آن‌ها کمک کنید تا مسئله را حل کنند. # ورودی در اولین خط ورودی، $n$ که نشان‌دهنده‌ی اندازه‌ی مثلث است و $m$ که تعداد مربّاهای داخل مثلث است، می‌آید. در ادامه $m$ خط می‌آید که در خط $i$ام، $r_i$ و $c_i$ آمده است که به ترتیب سطر و ستون خانه‌ی مربّای $i$ام را نشان می‌دهد. $$1 \leq n \leq 100\ 000$$ $$0 \leq m \leq 1000\ 000$$ $$1 \leq c_i < r_i \leq n$$ # خروجی در تنها خط خروجی، مقداری که بزرگ مربّا در معما خواسته را خروجی دهید. # مثال ### ورودی نمونه ۱ ``` 3 2 1 2 1 3 ``` ### خروجی نمونه ۱ ``` 1 ```  مجموعه شماره سطرهایی که زیرمثلث خوب می‌سازند عبارتند از: * $\{1\}$ * $\{2\}$ * $\{3\}$ * $\{1, 2\}$ * $\{1, 3\}$

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- مربّا چون خیلی در حل معما فرو رفته بود، یادش رفت تمرین های فیزیکش را انجام دهد. او هم اکنون در سر کلاس فیزیکش است و چیزی از مساحت زیر نمودار نمی داند. کپک حسود (معلم فیزیک مربّا) که از موضوع خبر دارد، برای تنبیه مربّا، هر ثانیه از $q$ ثانیه زنگ کلاس، یکی از دو کار زیر را انجام می دهد : 1. یک خط با عرض از مبدا $b_i$ و شیب $a_i$ روی تخته می کشد. 2. از مربّا می خواهد مساحت زیر نمودار $L_i$ تا $R_i$ را حساب کند. **در واقع شما در هر $x$، ارتفاع نمودار در آن $x$ را برابر ماکسیمم $y$ خطوط در آن $x$ فرض کنید.** مربّا که چیزی از این ها بلد نیست، از شما (کناردستی‌اش) می خواهد به سرعت پاسخ ها را برای اون محاسبه کنید. برای وضوح بیشتر به مثال ۲ مراجعه کنید. # ورودی در خط اول ورودی، عدد $q$، تعداد ثانیه های زنگ کلاس فیزیک می آید. در ادامه $q$ خط می آیند. خط $i$ ام، به یکی از دو صورت زیر است : $$1 \ a_i \ b_i$$ $$2 \ L_i \ R_i$$ که حالت اول نشان دهنده اضافه کردن خط توسط کپک حسود است و حالت دوم نشان دهنده یک پرسش از مربّا است. $$1 \leq q \leq 100\ 000$$ $$-10\ 000 \leq a_i, b_i \leq 10\ 000$$ $$0 \leq L_i < R_i \leq 20\ 000\ 000$$ # خروجی به ازای هر پرسش از مربّا، در یک خط، مساحت زیر نمودار را چاپ کنید. اختلاف مطلق و نسبی شما با جواب درست نباید بیش از $10^{-6}$ باشد. در واقع اگر جواب شما $p$ و جواب درست $j$ باشد، در صورتی جواب شما درست در نظر گرفته می‌شود که $\frac{|p - j|}{max(j, 1)} \le 10^{-6}$. # مثال ## ورودی نمونه ۱ ``` 2 1 1 0 2 0 1 ``` ## خروجی نمونه ۱ ``` 0.500000 ``` دقت کنید که $L , R$ گفته شده به حالت بسته - باز بر روی محور $x$ هاست. در نتیجه بازه $[0 , 1)$ ، شامل یک مثلث قائمه الزاویه به اضلاع قائمه $1$ خواهد بود که مساحت آن $0.5$ است. همچنین دقت کنید ممکن است این مقدار منفی هم باشد (در صورتی که تمام خط ها زیر محور $x$ ها بروند) همچنین اگر خطی کشیده نشده بود، مساحت زیر نمودار را ۰ در نظر بگیرید. ## ورودی نمونه ۲ ``` 6 1 -1 2 2 0 1 1 0 1 2 0 2 1 1 -1 2 0 3 ``` ## خروجی نمونه ۲ ``` 1.500000 2.500000 4.000000 ```