+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که فردی تنبل و طماع است، به پارک رفته است. پارک از بالا به شکل یک صفحه ی مختصات دکارتی است. رادزینکا در یک نقطه از پارک به مختصات $x$ و $y$ نشسته است و به افق خیره شده است(به طرف مثبت $y$ها). دوست رادزینکا که در مختصات $x_1$ و $y_1$ قرار دارد او را صدا میزند. رادزین میخواهد سرش را برگرداند، به او نگاه کرده و جوابش را بدهد. اما به دلیل تنبلی زیاد میخواهد سرش را در جهتی بچرخاند که کمترین مقدار چرخش را داشته باشد. به او کمک کنید که جهت درست را انتخاب کند # ورودی در سطر اول ورودی $x$ و $y$ آمده است محل نشستن رادزین را نشان میدهد. در سطر دوم دو عدد $x_1$ و $y_1$ آمده است که نشان دادن محلی است که دوست رادزینکا در آن قرار دارد. تضمین میشود در تست ها زاویه‌ی چرخش از چپ و راست متفاوت است. $$ -1000 \le x, y, x_1, y_1 \le 1000$$ # خروجی اگر باید به جهت راست حرکت کند "Right" و اگر باید در جهت چپ سرش را بچرخاند "Left" را خروجی دهید. # مثال ## ورودی نمونه ``` 2 2 3 1 ``` ## خروجی نمونه ``` Right ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (Rodzyanko Dobromil Vyacheslavovich) که یک آدم تنبل طماع است، با یک فیل در افتاده است! ماجرا از این قرار است که یک فیل شطرنج در خانه‌ی گوشه‌ی پایین سمت چپ یک صفحه‌ی شطرنج ۸*۸ قرار دارد و می‌خواهد به خانه‌ی گوشه‌ی بالا سمت راست برود. سطرها را از پایین به بالا و ستون‌ها را از چپ به راست به ترتیب با اعداد ۱ تا ۸ شماره‌گذاری می‌کنیم. پس فیل در خانه‌ی (۱،۱) قرار دارد و می‌خواهد به خانه‌ی (۸،۸) برود. همانطور که می‌دانید فیل شطرنج به صورت قطری حرکت می‌کند. خانه‌ی رادزینکا در خانه‌ی (۸،۸) صفحه‌ی شطرنج قرار دارد و اگر فیل بتواند به خانه‌ی او برسد، روی آن نشسته و از آنجایی که فیل است و سنگین، خانه خراب شده و رادزینکا خانه‌خراب می‌شود. از این رو رادزینکا می‌خواهد تعدادی از خانه‌های صفحه‌ی شطرنجی را ببندد تا فیل نتواند به خانه‌ی رادزینکا برسد. فیل نمی‌تواند به خانه‌های بسته شده برود یا حتی در مسیرش از آن‌ها رد شود. از طرفی چون رادزینکا تنبل است، می‌خواهد کمترین تعداد خانه را ببندد تا کمتر به زحمت بیفتد. متاسفانه رادزینکا نمی‌داند که کدام خانه‌ها را باید ببندد تا به هدفش برسد؛ برای همین از شما کمک می‌خواهد. از طرفی دوستان فیل (مثل اسب و سرباز و...) خانه‌ی (x,y) را در نظر گرفته‌اند و اگر رادزینکا بخواهد آن را ببندد، او را با شمشیر و جفتک لهِ له می‌کنند. پس رادزینکا نمی‌تواند خانه‌ی (x,y) را ببندد و شما باید موقع پیشنهاد دادن خانه‌ها، این را در نظر بگیرید. پس به این نکته دقت کنید که رادزینکا تمام خانه‌های صفحه‌ی شطرنج را می‌تواند ببندد غیر از خانه‌ی (۸،۸)، (۱،۱) و خانه‌ی (x,y) که در ورودی به شما داده می‌شود. # ورودی در تنها سطر ورودی به ترتیب دو عدد $x$ و $y$ آمده است که مختصات خانه‌ای را از جدول نشان می‌دهد که رادزینکا نمی‌تواند آن را ببندد. $$ 1 \le x,y \le 8 $$ حداقل یکی از بین $x$ و $y$ برابر 1 نیست. حداقل یکی از بین $x$ و $y$ برابر 8 نیست. # خروجی خروجی بدین شکل است: در سطر اول خروجی باید یک عدد باشد که نمایانگر تعداد خانه‌هایی است که رادزینکا باید ببندد. سپس در سطر‌های بعدی مختصات یکی از این خانه‌ها را باید به این صورت خروجی داد که عدد اول باید نمایانگر شماره‌ی سطر خانه و عدد دوم باید نمایانگر شماره‌ی ستون خانه باشد. # مثال ## ورودی نمونه ``` 4 4 ``` ## خروجی نمونه ``` 1 7 7 ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رادزینکا دوبرامیل ویچشسلافوویچ (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 ```