+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، نیاز به انرژی بیشتری برای خواب زمستانی دارد. از این رو به یک میوه‌فروشی رفته و می‌خواهد میوه بخورد تا انرژی بگیرد. او در ابتدا $k$ واحد انرژی دارد. میوه‌فروشی $n$ تا میوه دارد که با اعداد طبیعی نامگذاری شده‌اند و میوه‌ی i، مقدار $a_i$ انرژی به رادزینکا می‌دهد و مقدار $b_i$ انرژی از او می‌گیرد.(این انرژی به خاطر پوست کندن میوه است) پس دقت کنید که زمانی که رادزینکا می‌خواهد میوه‌ی $i$ را بخورد، باید حداقل به اندازه‌ی $b_i$ انرژی داشته باشد؛ زیرا این مقدار انرژی را باید صرف پوست کندن میوه کند و این مقدار از انرژی رادزینکا کم می‌شود. سپس او این میوه را می‌خورد و به انرژی‌اش $a_i$ تا اضافه می‌شود. رادزینکا می‌خواهد تعداد بزرگتر مساوی صفری از این میوه‌ها را انتخاب کرده و بخورد، طوری که در نهایت بیشترین انرژی را داشته باشد. به او بگویید که بیشترین انرژی که می‌تواند بدست بیاورد چقدر است. # ورودی در سطر اول ورودی دو عدد $n$ و $k$ آمده است که به ترتیب نمایانگر تعداد میوه‌ها و انرژی اولیه رادزینکا می‌باشد. سپس در هر یک از $n$ سطر بعدی یک میوه بدین صورت توصیف می‌شود: دو عدد $b_i$ و $a_i$ آمده‌اند که عدد اول نمایانگر انرژی است که رادزینکا باید برای خوردن میوه مصرف کند و عدد دوم نمایانگر انرژی است که میوه به رادزینکا می‌دهد. $$ 1 \le n \le 100\ 000 $$ $$ 0\le a_i,b_i,k \le 1\ 000\ 000\ 000 $$ # خروجی خروجی باید شامل یک عدد باشد که برابر بیشترین انرژی است که رادزینکا می‌تواند با خوردن تعدادی میوه بدست بیاورد. # مثال ## ورودی نمونه ۱ ``` 3 4 5 6 1 3 3 4 ``` ## خروجی نمونه ۱ ``` 8 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، باید درس تربیت بدنی را پاس کند. رادزینکا در دانشگاه تربیت دبیر زیولکوفسکی ایالت کالوگا (Tziolkovsky Kaluga State Pedagogical University) تحصیل میکند. همانطور که می‌دانید آزمون درس تربیت بدنی در این دانشگاه بسیار سخت گیرانه گرفته می‌شود، بصورتی که همه‌ی دانشجوها مقدار زیادی تمرین می‌کنند تا بتوانند از آن آزمون سخت گذر کنند. رادزینکا بدلیل تنبلی‌اش، قاعدتاً نمی‌تواند از پس این آزمون برآید. پس تلاش‌می‌کند که هرگونه حقه‌ای به کار گیرد تا بدون تلاش این درس یک واحدی را پاس کند. آزمون نهایی تربیت بدنی در این ترم، دوی استقامت است. دانشجویان باید $a$ متر دور زمین دو‌ و میدانی دانشگاه بدوند. این زمین $n$ متر طول دارد و شامل یک خط شروع است. کنار زمین $n$ خط کشیده شده‌است که هر دو تای آن ۱ متر با هم فاصله دارند و کنار هر خط فاصله‌ی نقطه‌ی شروع تا آن خط را نوشته است. بعنوان مثال، در کنار نقطه‌ی شروع، یک خط است که در کنار آن ۰ نوشته شده است. یک متر پیش از نقطه‌ی شروع نیز یک خط هست که در کنار آن مقدار $n - 1$ نوشته شده است. رادزینکا با کمی دقت متوجه شد که می‌تواند به جای $a$ متر، به مقدار باقی‌مانده‌ی $a$ پس از تقسیم بر $n$ متر ($a\ mod\ n$ متر) بدود و به جایی برسد که در نهایت باید آنجا متوقف شود! استاد تربیت بدنی این ترم، کاستاماروف لفانتونویچ (Kostomarov Lev Antonovich)، بسیار دقیق و سخت‌گیر است و برای تقلب جریمه‌های سنگینی می‌گذارد. اگر فردی که باید $x$ متر بدود به هر دلیلی این کار را انجام ندهد، باید بار دیگر امتحان بدهد و این‌بار $x^x$ متر بدود! رادزینکا هنگام دادن آزمون، با خیال راحت $a\ mod\ n$ متر می‌دود تا به کنار خط هدفش برسد. اما کاستاماروف دقیق‌تر از این حرف‌ها است و متوجه تقلب او می‌شود. پس با داد و بیداد، رادزینکا را به نقطه‌ی شروع می‌فرستد و به او می‌گوید که این بار باید $a^a$ متر بدود. رادزینکای سرخورده، به نقطه‌ی شروع می‌رود و دوباره دو را شروع می‌کند، و به کنار خط $a^a\ mod\ n$ می‌رود؛ اما باز هم کاستاماروف مچش را می‌گیرد و با چک و لگد، او را دوباره به نقطه ی شروع می‌برد که دوی ماراتن $(a^a)^{a^a}$ متری‌اش را آغاز کند. اکنون رادزینکا گیج شده و نمی‌تواند محاسبه کند که کجا باید توقف کند! شما مقدار $(a^a)^{a^a} \ mod \ n$ را به او بگویید تا یک بار دیگر برای فریب کاستاماروف تلاش کند. # ورودی در تنها سطر ورودی دو عدد $a$ و $n$ آمده است که با یک فاصله از هم جدا شده‌اند و به ترتیب نمایانگر مقدار اولیه‌ی دویدن در امتحان و طول زمین دو و میدانی دانشگاه تربیت دبیر زیولکوفسکی ایالت کالوگا است. $$1 \le a \le 1000$$ $$2 \le n \le 1000$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که نمایانگر خطی است که رادزینکا پس از ۲ بار تقلب، در انتهای امتحان باید کنارش بایستد. # مثال ## ورودی نمونه ۱ ``` 2 1000 ``` ## خروجی نمونه ۱ ``` 256 ``` ## ورودی نمونه ۲ ``` 2 5 ``` ## خروجی نمونه ۲ ``` 1 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک فرد تنبل طماع است، باید شیر بخرد. رادزینکا را صبح مادرش بیدار کرد به مزرعه فرستاد تا برای صبحانه شیر تازه بیاورد. اما او چون تنبل است به فروشگاه رفته و در حال خرید شیر پاکتی است. در کنار فروشگاه یک نانوایی بوده و صف آن نیز بسیار بلند است به طوری که $10^9$ نفر در صف آن قرار دارند. متاسفانه مغازه‌دار در فروشگاه شیر پاکتی نداشت و به انبار رفت تا بیاورد. برای همین رادزینکا باید مدتی منتظر بماند و از روی بیکاری جایگاه هر شخصی را در صف نانوایی یادداشت کرد. از آنجایی که صف نانوایی طولانی است و بعضی از افراد مثل رادزینکا پیرژامه مامان‌دوز پوشیده‌اند و خیابان پر از آدم است، بعضی از افراد تصمیم می‌گیرند که تا آبرویشان نرفته، به خانه بروند و لباس مناسب پوشیده و به صف برگردند. برای همین تمام افرادی که پشت این آدم‌ها بودند، یک عدد به جلو آمده و جایگاهشان یک عدد کمتر می‌شود. متاسفانه زمانی که این افراد به صف برمی‌گردند، جای قبلیشان یادشان نیامده و به یک جای جدید در صف می‌روند. در ضمن تا وقتی که نفر قبلی که به خانه رفته، به صف برنگردد، نفر جدیدی از صف خارج نمی‌شود. در همین حین، رادزینکا تمام جابه‌جایی‌ها را یادداشت می‌کند؛ یعنی به ازای هر شخصی که از صف خارج شده و به آن برمی‌گردد، برایش یادداشت می‌کند که زمانی که رادزینکا وارد فروشگاه شد در چه جایگاهی بود و موقع بازگشت جلوی نفر چندم صف قرار گرفت. فقط دقت کنید که بعضی از افراد امکان دارد که چندبار به خانه رفته و برگردند چرا که کندذهن اند و وقتی به خانه می‌روند یادشان می‌رود که لباسشان را عوض کنند و فکر می‌کنند که آمده‌اند خانه تا آب بخورند. برای همین دوباره با همان پیرژامه مامان‌دوز به صف برمی‌گردند. متاسفانه رادزینکا گیج شده‌است. (قبلا گیج نبود) او الان می‌خواهد یک سری اطلاعات به دست بیاورد و برای این کار از شما کمک گرفته‌است. او تمام اطلاعاتی را که از جابه‌جایی‌ها یادداشت کرده به شما می‌دهد و از شما دو نوع اطلاعات می‌خواهد: در نوع اول او از شما می‌خواهد که به او بگویید که شخصی که الان در جایگاه $x$ از صف قرار دارد، هنگام ورود رادزینکا به فروشگاه در کدام جایگاه قرار داشته است. در نوع دوم او از شما می‌خواهد که به او بگویید که شخصی که در زمان ورود رادزینکا به فروشگاه در جایگاه $x$ قرار داشت، الان در چه جایگاهی از صف قرار دارد. # ورودی در سطر اول ورودی $q$ آمده است که نمایانگر تعداد جابه‌جایی‌ها است. سپس در هر خط توصیف یک جابه‌جایی آمده است: هر جابه‌جایی شامل دو عدد $z$ و $y$ است. عدد اول نمایانگر این است که شخصی که در زمان ‍‍‍‍‍‍‍ورود رادزینکا به فروشگاه از صف خارج شده، قبل از خارج شدن و عدد دوم نمایانگر جایگاه شخصی است که شخص از صف خارج شده بعد از بازگشت از خانه به جلوی او رفته است. جابه‌جایی‌ها به ترتیب زمانی آمده است. سپس درس سطر بعدی یک عدد $n$ آمده است که نمایانگر تعداد درخواست‌های رادزینکا از شما است. سپس در هر خط توصیف یک درخواست آمده است: ابتدا یک حرف انگلیسی می‌آید که نشان می‌دهد که درخواست رادزینکا از نوع اول است یا دوم. حرف $L$ نمایانگر درخواست نوع اول و حرف $P$ نمایانگر درخواست از نوع دوم است. سپس $x$ آمده است که توضیحات این ورودی در قسمت توضیحات انواع درخواست آمده است. $$ 1\le q,n \le 50\ 000 $$ $$ 1 \le x,z,y \le 1\ 000\ 000\ 000 $$ # خروجی خروجی باید شامل $n$ خط باشد که در خط i، باید جواب درخواست i آمده باشد. # مثال ## ورودی نمونه ۱ ``` 2 6 3 9 6 8 L 1 L 2 L 3 L 4 P 1 P 2 P 3 P 4 ``` ## خروجی نمونه ۱ ``` 1 2 9 6 1 2 5 6 ``` ## ورودی نمونه ۲ ``` 5 7 2 2 7 9 7 10 1 100005 99995 9 L 1 P 2 L 2 P 7 L 7 P 9 P 10 P 99999 L 100000 ``` ## خروجی نمونه ۲ ``` 10 3 1 5 4 4 1 100000 99999 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که فردی تنبل و طماع است، میخواهد به خانه‌ی مادربزرگش برود. رادزینکا در شهر استاوروپل زندگی میکند و مادربزرگ او در چیرکیسک میزید. روسیه به شکل یک جدول خیلی بزرگ است(روسیه کشور بزرگی است). سطرها و ستون‌های جدول با اعداد صحیح شماره گذاری شده است و خانه‌ی واقع در سطر i و ستون j را (i, j) مینامیم. استاوروپل در خانه (0, 0) این جدول وجود دارد و چیرکیسک در (x, y) است. رادزینکا در هر مرحله میتواند به خانه‌‌هایی که مجاور ضلعی خانه‌ی فعلی خود در جدول است، برود. در روسیه رشته کوه های بسیاری وجود دارد که در جدول به شکل مستطیل‌هایی موازی با سطر و ستون‌های جدول است. هیچ دو رشته کوهی با هم تقاطع نداشته و حتی مماس هم نیستند. به دلیل سرمای زیاد رادزینکا نمیتواند به کوهستان وارد شود. شما باید به رادزینکا کمک کنید تا طول کوتاه‌ترین مسیر از استاوروپل به چیرکسیک را بیابد. # ورودی در سطر اول ورودی دو عدد $x$ و $y$ آمده است که نمایانگر موقعیت چیرکیسک در جدول است در سطر دوم عدد $n$ آمده که برابر تعداد رشته کوه‌ها(مستطیل‌ها) است. سپس در $n$ سطر بعدی در هر سطر چهار عدد $x_1$ و $y_1$ و $x_2$ و $y_2$ که نشان دهنده‌ی دو راس مقابل به هم مستطیل(رشته کوه) است. $$ 1 \le n \le 100\ 000 $$ $$ 1 \le x, x_1, x_2 \le 1\ 000\ 000 $$ $$ -1\ 000\ 000 \le y, y_1, y_2 \le 1\ 000\ 000 $$ # خروجی در سطر اول خروجی طول کوتاه‌ترین مسیر باید چاپ شود. # مثال ## ورودی نمونه ۱ ``` 9 1 2 5 -3 8 3 10 -3 13 3 ``` ## خروجی نمونه ۱ ``` 16 ``` ## ورودی نمونه ۲ ``` 12 0 5 2 -1 3 1 6 -7 8 -1 6 1 8 6 4 3 4 5 10 -5 10 3 ``` ## خروجی نمونه ۲ ``` 24 ```