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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آی مجری که به فکر بچه‌ها است، می‌خواهد آن‌ها را به یک اردوی علمی ببرد. در این اردو او آن‌ها را به خارج از شهر (در یک بیابان) برده و در آنجا یک مسابقه‌ی آموزشی برگزار می‌کند. آی مجری $n$ نقطه را در بیابان مشخص کرده و بین یکسری از نقاط خط کشیده به طوری که از هر نقطه به هر نقطه‌ی دیگری دقیقا یک مسیر از روی خطوط وجود دارد. حال آی مجری روی هر خط و در طول مسیر بین دو نقطه مسائلی قرار می‌دهد که اگر کسی از روی آن‌ها عبور کند به اندازه‌ی سختی مسئله به علمش اضافه می‌شود. دقت کنید که سختی هر مسئله عددی **طبیعی** می‌باشد. آی مجری در اول کار به هرکس دو نقطه متفاوت را می‌دهد و می‌گوید باید از نقطه‌ی اول به نقطه‌ی دوم برود. علمی که به یک نفر اضافه می‌شود برابر است با مجموع علمی که در مسیر به دست می‌آورد. بچه‌ها اصلا دوست ندارند به اندازه‌ی هم به علمشان اضافه شود(مثلا اگر فامیل و جیگر به اندازه‌ی هم علم کسب کنند، فامیل بسیار ناراحت می‌شود). برای همین آی مجری می‌خواهد ببیند با تغییر مسائل حداقل و حداکثر چند نفر را می‌تواند با خود ببرد تا همه علم متفاوتی کسب کنند. # ورودی در سطر اول ورودی، عدد $n$ آمده‌است که نمایانگر تعداد نقاط است. $$1 \le n \le 100\ 000$$ سپس در $n - 1$ سطر بعدی در هر سطر دو عدد $x$ و $y$ می‌آید که یعنی نقطه‌ی $x$ به نقطه‌ی $y$ وصل است. تضمین می‌شود که ورودی شروط ذکر شده در صورت سوال را دارد. $$1 \le x, y \le n$$ # خروجی خروجی شامل دو عدد است که به ترتیب نشان‌دهنده‌ی حداقل و حداکثر تعداد بچه‌هاییست که آی مجری می‌تواند با خود ببرد و علمی که هرکدام کسب می‌کنند متفاوت باشد. # مثال ## ورودی نمونه ۱ ``` 2 1 2 ``` ## خروجی نمونه ۱ ``` 1 1 ``` ## ورودی نمونه ۲ ``` 4 1 2 2 3 3 4 ``` ## خروجی نمونه ۲ ``` 3 6 ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- آی مجری که به فکر بچه‌ها است، تصمیم گرفته برای اولین بار آن‌ها را به سینما ببرد. آی مجری می‌داند که اگر یکی از بچه‌ها هنگام دیدن فیلم ناراحت باشد، فیلم را به کام همه تلخ خواهد‌کرد. به همین دلیل می‌خواهد همه راحت باشند. و اگر چنین چیزی امکان نداشت اصلا به سینما نروند. یکی از بچه‌‌ها ناراحت است اگر فردی جلوی او(نزدیک تر به پرده‌ی سینما و هم‌ستون با او) نشسته باشد و قدش از او بلندتر باشد. همچنین به دلیل این که آن‌ها خیلی خوش‌قلب هستند اگر بیننده‌ی دیگری غیر از آن‌ها هم نتواند فیلم را به خوبی ببیند(فرد بلندتری جلویش نشسته باشد)، ناراحت می‌شوند. همه‌ی انسان‌ها در سه دسته‌ی قدی دسته‌بندی می‌شوند: ۱) انسان‌های کوتاه(تا ۱۹۰ سانتی‌متر) ۲) انسان‌های معمولی(۱۹۱-۱۹۸سانتی‌متر) ۳) انسان‌های بلند(۱۹۹ به بالا) در واقع افرادی نمی‌توانند درست ببینند که یک نفر از دسته‌ی بلند‌تر جلوی آن‌ها نشسته باشد. صندلی‌های سینما $r$ ردیف و $c$ ستون دارند که در ردیف آخر نزدیک ترین آدم‌ها به پرده‌ی سینما نشسته‌اند. قبل از رسیدن بچه‌ها تعدادی بیننده به سالن سینما رفته اند و در جاهای دلخواه خود نشسته‌اند و نمی‌توان جای آن‌ها را تغییر داد. شما باید یک ترتیب دلخواه از نشستن همه‌ی بچه‌ها در سینما خروجی دهید که همگی راحت باشند و یا این که بگویید بهتر است اصلا به سینما نروند و به جای آن به پارک بروند. # ورودی در سطر اول ورودی دو عدد طبیعی $r$ و $c$ آمده‌است، که به ترتیب نمایانگر تعداد ردیف‌ها و ستون‌های سینماست. سپس در $r$ سطر بعدی در هر کدام $c$ کاراکتر آمده‌است که به این نحو معنی می‌شوند: ۱) جای خالی: # ۲) انسان کوتاه: s ۳)انسان معمولی: n ۴)انسان بلند: t در سطر بعدی سه عدد طبیعی و کوچکتر از یک میلیون می‌آید که به ترتیب نشان‌دهنده‌ی تعداد بچه‌های کوتاه، معمولی و بلند است که آی مجری می‌خواهد با خود به سینما بیاورد. $$1 \le r, c \le 1000$$ # خروجی اگر حالتی وجود نداشت، "Let's go to the park" را چاپ کنید. در غیر این صورت باید یک جدول مانند ورودی چاپ کنید که همه‌ی بچه‌ها نیز در جاهای خالی آن نشسته‌اند. اگر چند حالت وجود داشت،‌ به دلخواه یکی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 ### #s# n## 2 1 1 ``` ## خروجی نمونه ۱ ``` t## ns# nss ``` قبل از رسیدن آی مجری و بچه‌ها دو نفر با قد‌های کوتاه و متوسط روی صندلی‌ها نشسته‌اند. فرد با قد متوسط در نزدیک ترین فاصله به پرده نشسته‌است. آی مجری ۴ نفر را با خود برده است. دو نفر با قد کوتاه، یک نفر با قد متوسط و یک نفر با قد بلند. یک حالت دلخواه از نشستن بچه‌ها را در خروجی می‌بینید. ## ورودی نمونه ۲ ``` 4 4 #### ##tn nt#s ##t# 4 3 2 ``` ## خروجی نمونه ۲ ``` Let's go to the park ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آی مجری که به فکر بچه‌ها است، یادش رفته است که به فکر بچه‌ها است! او به جای قصه‌ی شبانگاهی می‌خواهد یک بازی راه بیاندازد تا بچه‌ها به سر کار بروند(فردا متوجه این موضوع می‌شوید) و خودش راحت بخوابد. او یک رشته بزرگ به بچه‌ها می‌دهد که فقط از ارقام تشکیل شده است. سپس از آنها می‌خواهد که تعداد زیر رشته‌های این رشته را پیدا کنند که اگر این زیر رشته را به عنوان یک عدد در نظر بگیریم، این عدد بر عدد اول $p$ بخش پذیر است. اگر کسی جواب درست را بدهد، آی مجری به او به اندازه‌ی آن عدد شیرینی خواهد داد. متاسفانه از آنجایی که بچه‌ها جواب این سوال را نمی‌دانند، سعی می‌کنند که هی عدد بپرانند تا اینکه آی مجری بگوید که درست گفته‌اند و شیرینی‌ها را به آن‌ها بدهد؛ اما برای اینکه شیرینی بیشتری بگیرند تلاش می‌کنند که عددهای بزرگی را به عنوان جواب به آی مجری بگویند غافل از اینکه جواب عدد بزرگی نیست... آن‌ها هی عدد می‌پرانند و آی مجری مجبور است که به آن‌ها بگوید که جوابشان درست است یا خیر و اینگونه است که نمی‌تواند بخوابد و چون اعداد بچه‌ها از جواب خیلی دور است متاسفانه آی مجری به این زودی‌ها نمی‌تواند بخوابد. حالا آی مجری از ایده‌اش پشیمان شده است و می‌خواهد خود جواب را بگوید و به همه شیرینی بدهد و مثل همیشه برایشان قصه بخواند تا خوابشان ببرد و او هم بتواند بخوابد اما متاسفانه الان دیر وقت است و او جواب را یادش نمی‌آید. به او کمک کنید که جواب را پیدا کند. # ورودی ورودی شامل دو خط است که در خط اول رشته‌ مورد نظر می‌آید و در خط دوم عدد اول $p$. $$ 2 \le p \le 10^9 $$ طول رشته حداکثر $10^6$ می‌باشد. رشته تنها از ارقام تشکیل شده است. # خروجی در تنها سطر خروجی تعداد زیررشته‌هایی از رشته‌ی ورودی را خروجی دهید که عدد متناظر با آن زیر رشته‌ بر $p$ بخش پذیر است. # مثال ## ورودی نمونه ۱ ``` 3146 3 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 1313 13 ``` ## خروجی نمونه ۲ ``` 3 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- آی مجری که به فکر بچه‌ها است، می‌خواهد برای فامیل دور(که فردا بیشتر با او آشنا می‌شوید) تولد بگیرد. او با دیدن در به وجد می‌آید. آی مجری برای تولد او یک فضا طراحی کرده است که در آن $n$ در پشت سر هم قرار دارند. در ورای در $i$م، $a_i$ در دیده می‌شود. برای روز تولد فامیل، آي مجری $m$ برنامه دارد. در هر برنامه او به فامیل سه عدد $l$ و $r$ و $k$ می‌دهد که به این معنی است که فامیل می‌تواند از در $l$م شروع کرده و آن‌را باز کند و سپس به $k$ در جلوتر رفته و آن را باز کند و همین‌طور ادامه دهد تا به در $r$م برسد. مقدار خوش‌حالی فامیل در هر برنامه برابر تعداد در هاییست که در ورای در های باز‌شده می‌بیند. آی مجری می‌خواهد تولد به یاد ماندنی‌ای برای فامیل تدارک ببیند. برای همین شما باید به او کمک کنید تا بداند در هر برنامه چقدر فامیل خوش‌حال می‌شود. # ورودی در سطر اول ورودی دو عدد طبیعی $n$ و $m$ آمده‌است، که نشان‌دهنده‌ی تعداد در های اولیه و تعداد برنامه‌های روز تولد است. در سطر دوم $n$ عدد می‌آید که عدد $i$م نشان‌دهنده‌ی $a_i$ است. در $m$ سطر بعدی در هر سطر سه عدد $l$ و $r$ و $k$ می‌آید که نمایانگر یک برنامه هستند. تضمین می‌شود که $r - l$ بر $k$ بخش‌پذیر است. $$1 \le a_i \le 10^9$$ $$1 \le l \le r \le n \le 100\ 000$$ $$1 \le k \le n \le 100\ 000$$ $$1 \le m \le 300\ 000$$ # خروجی خروجی شامل $m$ عدد است که عدد $i$م نمایانگر مقدار خوش‌حالی فامیل دور در برنامه‌ی$i$م است. # مثال ## ورودی نمونه ``` 5 5 1 2 3 4 5 1 5 1 1 5 2 1 4 3 1 5 4 1 1 5 ``` ## خروجی نمونه ``` 15 9 5 6 1 ```

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آی مجری که به فکر بچه‌ها است، تصمیم گرفته است که گابی را به مسابقات شنا بفرستد تا او با شنا مشغول شده و لاغر شود اما مشکلی که وجود دارد این است که گابی از آب می‌ترسد. آی مجری فرایندی را برای ریختن ترس گابی از آب طراحی کرده است که به آن فرایند ترس‌ریزی می‌گویند و روی دنباله‌ی $a$ به این صورت اجرا می‌شود: او ابتدا تعدادی استخر را پر از آب می‌کند که عمق استخر $i$، $a_i$ می‌باشد. سپس با کمک بقیه گابی را به استخر شماره‌ی ۱ می‌اندازد و گابی که نمی‌تواند از آن بیرون بیاید، در آن می‌ماند و ترسش از استخری با عمق $a_1$ و کمتر می‌ریزد. سپس آی مجری گابی را از استخر شماره‌ی ۱ بیرون می‌آورد و از بین اعداد ۲ تا $n$ کوچکترین عدد (مانند $j$) را انتخاب می‌کند که $a_1<a_j$ و گابی را در درون استخر $j$ می‌اندازد تا ترسش از عمق کمتر از آن هم بریزد. سپس او همین کار را ادامه می‌دهد و استخر دیگری با شماره‌ی $k$ انتخاب می‌کند که $k>j$ و $a_k>a_j$. سپس همینکار را ادامه می‌دهد(یعنی جلو می‌رود تا استخری با عمق بیشتر از قبلی را پیدا کند و گابی را درون آن بیاندازد) تا به پایان دنباله برسد. حالا اگر در این فرایند ترس‌ریزی آی مجری گابی را $d$ بار درون آب بیاندازد، مقدار خوبی این فرایند $d$ می‌شود. به تازگی نزدیک خانه‌ی آی مجری مغازه‌ای باز شده است که توانایی ساختن استخر‌هایی با $n$ عمق متفاوت $b_1$، $b_2$، $b_3$ ... $b_n$ را دارد. حالا آی مجری به این صورت می‌خواهد به این مغازه سفارش دهد که برایش یک فرایند ترس‌ریزی بسازد: او به مغازه دار چهار عدد $l_1$، $r_1$، $l_2$ و $r_2$ را می‌دهد و آقای مغازه دار یک فرایند ترس‌ریزی با استخر‌هایی با عمق‌های زیر برای او می‌سازد: $$b_{l_1}, b_{l_1+1} , b_{l_1+2} , ... , b_{r_1} , b_{l_2}, b_{l_2+1} , b_{l_2+2} , ... , b_{r_2} $$ آی مجری بین $q$ درخواست که می‌تواند به مغازه‌دار بدهد تا برایش فرایند ترس‌ریزی درست کند مانده است که کدام را انتخاب کند. برای همین او از شما می‌خواهد مقدار خوبی هر فرایند را خروجی دهید تا او بتواند با دست بازتری انتخاب کند. # ورودی در سطر اول ورودی دو عدد $n$ و $q$ می‌آید که عدد اول نمایانگر تعداد عمق‌های متفاوتی است که مغازه‌دار می‌تواند بسازد و عدد دوم نمایانگر تعداد در‌خواست‌هایی است که آی مجری می‌تواند به مغازه‌دار بدهد. سپس در سطر دوم $n$ عدد می‌آید که عدد $i$، $b_i$ می‌باشد. بعد از آن ورودی $q$ سطر دارد که در سطر $i$، درخواست $i$ ام به صورت چهار عدد $l_1$، $r_1$، $l_2$ و $r_2$ می‌آید. $$ 1 \le n,q \le 500\ 000 $$ $$ 1 \le b_i \le 10^9 $$ # خروجی خروجی شامل $q$‌ سطر است که سطر $i$، شامل مقدار خوبی فرایند ترس‌ریزی است که مغازه‌دار با استفاده از در‌خواست $i$ ام آی مجری می‌تواند بسازد. # مثال ## ورودی نمونه ۱ ``` 3 2 1 5 7 1 2 2 3 1 2 3 3 ``` ## خروجی نمونه ۱ ``` 3 3 ``` فرایند ساخته شده با استفاده از درخواست اول: 1،5،5،7 فرایند ساخته شده با استفاده از درخواست دوم: 1،5،7 ## ورودی نمونه ۲ ``` 3 2 5 1 7 1 3 1 2 1 1 3 3 ``` ## خروجی نمونه ۲ ``` 2 2 ``` فرایند ساخته شده با استفاده از درخواست اول: 5،1،7،5،1 فرایند ساخته شده با استفاده از درخواست دوم: 5،7

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آی مجری که به فکر بچه‌ها است، می‌خواهد به آن‌ها آجیل بدهد، اما همانطور که در سوال های قبل ذکر شد، مشکلات مالی به آی مجری فشار آورده. برای همین او می‌خواهد فقط به تعدادی از آن‌ها آجیل بدهد. برای این‌کار او یک مسابقه طراحی کرده‌است که در آن بچه ها با هم مسابقه دهند و فقط تعدادی از آن‌ها به آجیل برسند. زمین مسابقه به صورت یک درخت ریشه‌دار است، که ریشه‌ی آن راس شماره‌ی یک است. برای شروع بچه‌ی $i$م، روی راس $p_i$ ایستاده‌است. $p_i$ها همگی برگ هستند. در ضمن مکان اولیه‌ی هیچ دو بچه‌ای برابر نیست. بچه‌ی $i$م، با سرعت $v_i$ می‌تواند از درخت بالا برود. هر یال درخت یک طول دارد. هربار که تعدادی از بچه‌ها همزمان به هم می‌رسند(در وسط یال‌ها و یا در رئوس)، همدیگر را می‌بینند و بعد از سلام و احوال پرسی(سلام و احوال‌پرسی زمانی نمی‌گیرد) سرعت یکدیگر را می‌پرسند و اگر کسی سرعتش کمتر از یکی از افراد دیگر باشد ناامید شده و دیگر ادامه نمی‌دهد(احترام به بزرگتر هم زمانی نمی‌گیرد). اگر سرعت چند نفر با هم مساوی باشد، کسی که شماره‌ی بزرگتر دارد جلو می‌رود و بقیه به احترام بزرگتر دیگر ادامه نمی‌دهند. در پایان آی مجری می‌خواهد بداند کدام بچه‌ها موفق می‌شوند به ریشه‌ی درخت برسند. **دقت کنید که بچه‌ها به محض رسیدن به ریشه آجیل را می‌گیرند و دیدار‌های در ریشه مهم نیست.** آی مجری اگر تعداد دقیق بچه‌ها را محاسبه کنید، به شما هم یک بسته آجیل به عنوان هدیه می‌دهد. # ورودی در سطر اول ورودی دو عدد $n$ و $m$ آمده‌است که به ترتیب نمایانگر تعداد رئوس و تعداد بچه‌ها است. در سطر دوم $m$ عدد آمده است، که عدد $i$م نشان‌دهنده‌ی $v_i$ است. در سطر سوم $m$ عدد دیگر آمده‌است که عدد $i$م برابر $p_i$ است که نشان‌دهنده‌ی مکان اولیه‌ی بچه‌ی شماره $i$ است. تضمین می‌شود تمام این رئوس برگ هستند. همچنین تضمین می‌شود همه‌ی $p_i$ها متفاوت‌اند. در $n - 1$ سطر بعدی در هر سطر سه عدد می‌آید که دو عدد اول نشان‌دهنده‌ی دو سر یک یال هستند و راس بعدی نشان‌دهنده‌ی طول یال($w_i$) است. $$1 \le n, m \le 100\ 000$$ $$1 \le p_i \le n$$ $$1 \le v_i, w_i \le 10^9$$ # خروجی در سطر اول خروجی یک عدد چاپ کنید که نشان‌دهنده‌ی تعداد افرادی است که به ریشه می‌رسند و آجیل دریافت می‌کنند. در سطر بعدی شماره‌ی افرادی را که آجیل دریافت می‌کنند را به ترتیب صعودی (ترتیبی که در ورودی آمده‌اند) چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 2 3 4 3 4 1 2 2 2 3 3 2 4 4 ``` ## خروجی نمونه ۱ ``` 1 2 ``` ## ورودی نمونه ۲ ``` 4 2 3 3 3 4 1 2 2 2 3 3 2 4 4 ``` ## خروجی نمونه ۲ ``` 2 1 2 ```