+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی از رجل سی اسی است و بخاطر همین پس از اتفاق رخ داده و پخش شدن شایعات بسیار مورد هجمه ی خبرنگاران اقشار مختلف دانشکده ی ریاضی قرار گرفته است. مهدی که به ایزیف نیز مشهور است به درگیری با خبرنگاران میپردازد و خبرنگاران قشر های مختلف را با تکنیک هایی که در داعش آموخته منفجر می کند. وی در هر مرحله خبرنگاران را به صف کرده و سپس هر سری خبرنگار های متوالی که به یک شبکه تعلق داشته باشد و تعداد آنها حداقل 3 تا باشد را به صورت همزمان منفجر می کند.سپس با همان ترتیب خبرنگاران باقی مانده را به صف کرده و دوباره عملیات را انجام میدهد. ابوبکر البغدادی میخواهد بداند در انتها چه میشود .از اونجایی که زمان کافی برای تلف کردن نداره از شما میخواد که اینکار رو واسش انجام بدین. # ورودی یک رشته به طول n ) n در واقع تعداد خبرنگاران میباشد ) که عدد i ام شبکه خبرنگار i ام در صف اولیه است ( شماره ی شبکه هر فرد یک رقمی است ، 0 تا 9 ) $n<10^5$ # خروجی یک رشته شامل شماره شبکه ی افرادی که سالم باقی ماندند . اگر هیچ خبرنگاری جان سالم به در نبرده بود عبارت null را چاپ کنید . # مثال ## نمونه ورودی 1: 12221112 ## نمونه خروجی 1: 12 همزمان 3 تا 1 و 3 تا 2 منفجر میشوند سپس دوباره به صف میکند و اتفاقی نمیافتد ## نمونه ورودی 2: 1122111221 ## نمونه خروجی 2: null ابتدا 3 تا 1 منفجر میشوند بعد از دوباره به صف کردن 4 تا 2 منفجر میشوند و در انتها 3 یک باقی مانده بعد از به صف شدن منفجر میشوند .

+ محدودیت زمانی: ۲ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی ایزی( ـُ ف) میخواد به دانشگاهش خدمت کنه پس تصمیم گرفته عضو شورای صنفی بشه.هدفش کوتاه کردن دست خبرنگاران از دانشگاهه.مهدی با شعار" ما برای **فرد**ای بهتر آمده ایم" تبلیغات خود در انتخابات رو انجام میده و برای اثبات صدق و درستی و کذب محض نبودن حرفاش پیش رئیس دانشگاه میره و شعار خودشو فریاد میزنه و میگه همه ی دانشکده های منتهی به زوج خیابون باید منتهی به فرد خیابون بشن! رئیس دانشگاه هم که شخصیت خفن و با اعتباری مثل مهدی ایزی اونم با هدفی به این والایی و در راستای اهداف دانشگاه رو میبینه ،فورا دستور میده که همه ی خیابون های در راستا تخریب شن!ا ما چون مهدی باید به کارهای تبلیغاتی خود برسه،پس از شما میخواد که جوری خیابونارو تخریب کنین که هر دانشکده فرد خیابون داشته باشه و اگر نمیشه بگین نمیشه! (دقت کنید که لازم نیست خیابان های تخریب شده مینیمم باشد! صرفا یک حالت درست برای تخریب خیابان ها ارائه دهید) # ورودی در خط اول دو عدد طبیعی $n$ و $m$ قرار دارد که به ترتیب تعداد دانشکده ها و خیابان هاست. (دانشکده ها از $1$ تا $n$ شماره گذاری شده اند) $n, m<10^5$ در $m$ خط بعدی، در خط $i$ام دو عدد $a_i$ و $b_i$ قرار دارد به این معنی که بین این دو دانشکده یک خیابان قرار دارد. # خروجی در صورتی که امکان ندارد که این کار را بکنیم، $-1$ چاپ کنید. در غیر این صورت ابتدا عدد $k$، تعداد یال هایی که باید حذف شوند، و در $k$ خط بعدی اندیس خیابان هایی که باید حذف شوند را چاپ کنید. (اندیس خیابان ها از $1$ تا $m$ به ترتیب ورودی است) # مثال ## ورودی نمونه 4 4 1 2 2 3 3 4 1 4 ## خروجی نمونه 2 1 3

+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از اینکه راه ها تخریب شدند و گند بزرگی در دانشگاه بالا اومد و قیافه ی دانشکده ها مثل شهرهای سوریه پس از حملات داعش شده بود،رئیس دانشگاه تصمیم به شکنجه کردن ایزیف گرفت و این کار رو به "PAP" سپرد.PAP برای این که مهدی رو در چشم همه ی عالمیان خوار و حقیر کنه دستور به طراحی تلویزیون شبکه بندی شده ی بزرگ m در n ای(هر شبکه برای یک دانشکده در دانشگاه ها!!!) داد که از سرتاسر دانشگاه همه ی آدم ها بتونن به فلاکت کشیده شدن ایزیف رو ببینن.اما از اونجایی که پس از ساخته شدن این تلویزیون در دسترس همه بود،برای اینکه هیچ کسی نتونه از این تلویزیون سوء استفاده بکنه،این تلویزیون رو کد گذاری کرد به این صورت که تا قبل از روز موعود تلویزیون فقط به این صورت کار میکند: ابتدا در همه ی خونه ها عدد 0 نوشته شده است. یا مختصات یک زیر تلویزیون داده میشه و k هم داده میشه و k واحد به همه ی خونه ها اضافه میشه. یا مختصات یک زیر تلویزیون داده میشه و مجموع اعداد داخل اون خواسته میشه. وقتی آن روز بزرگ که همه ی عالمیان منتظرش هستن فرا میرسه، باید تلویزیون دوباره کاربرد اصلی خودشو بدست بیاره. اما این کار فقط در صورتی ممکنه که کد این برنامه دوباره به تلویزیون داده شود. اما از اونجایی که فلش حاوی کد دست محمدرضا بوده و محمدرضا این فلش رو گم کرده(البته اون همیشه فلشها رو گم نمیکنه!)، پس شما باید این کد رو بزنین! # ورودی در خط اول سه عدد q, m,n می آید. n,m<=1000 q<=10000 k<=10^9 سپس در q خط بعدی هر خط یک دستور وجود دارد. دو نوع دستور داریم ۱) اضافه کردن عدد k به زیرمستطیل با دادن گوشه های مستطیل add x1 y1 x2 y2 k ۲) گرفتن مجموع اعداد زیر مستطیل ask x1 y1 x2 y2 (در نصف تست کیس ها اول همه ی دستورات نوع اول آمده اند و سپس دستورات نوع دوم) # خروجی هنگام ورود دستورات نوع دوم، مجموع عدد زیر مستطیل را خروجی دهید. # مثال ## نمونه ورودی 5 5 5 add 3 4 5 4 8 ask 1 3 3 4 ask 1 1 2 4 add 4 3 4 4 8 ask 1 5 2 5 ## نمونه خروجی 8 0 0

+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- قبل از اجرای حکم به صلیب کشیده شدن،PAP برای اینکه ایزیف رو مفلوک تر کنه،دستور میده که اونو روی گاری اسبی تک شاخ و سفید با خال های سیاه به صورت عمود بر اسب ببندن و توی سطح دانشگاه بچرخونن تا همه اونو ببینن.اما برای اینکه این اتفاق بیفته PAP مجبور بود که دانشگاه رو به مستطیل m در n ای شبکه بندی کنه و تعداد آدمایی که تو یه ساعت از هر شبکه رد میشن رو اندازه بگیره و توی شبکه ها بنویسه تا علاوه بر له کردن مهدی،خفن بودن خودشو هم نشون بده.PAP میخواد که یک مسیر با شبکه هایی با اعداد صعودی اکید طی بشه تا بیشترین آدما سرنوشت پوچ و حبط شده ی ایزیف رو ببینن. گاری هر مرحله میتونه از خونه ای که هست به 4 خونه ی بالا، پایین، چپ و راستش بره! بعد از اینکه PAP اعداد رو یادداشت کرد، نیاز به یه درشکه چی داره که این مسیر رو طی کنه.اما از اونجایی که آدم لایق تر باید برای این کار انتخاب شه و همه ی شما شدیدا مشتاقید، پس PAP از شما میخواد که کد این کار رو بزنین تا بتونه بهترین انتخاب رو داشته باشه! # ورودی در خط اول دو عدد n و m طول و عرض مستطیل(شبکه) در n خط بعدی که در خط iام m عدد که اعداد سطر i ام جدول است داده میشود. $n, m<10^3$ اعداد جدول حسابی و حداکثر 9 رقمی است . # خروجی طول بزرگترین مسیر برای گاری که اعداد مسیر صعودی اکید باشند. # مثال ## ورودی نمونه ۱ 3 4 5 6 1 10 3 7 3 13 19 1 1 3 ## خروجی نمونه ۱ 4 ## ورودی نمونه ۲ 3 3 1 2 4 2 6 4 12 5 9 ## خروجی نمونه ۲ 3 ## توضیح درشکه میتواند به ترتیب خانه های ۱ ، ۲ و ۶ را بپیماید.

+ محدودیت زمانی: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از گردوندن مهدی ایزیُف در سطح دانشگاه PAP متوجه میشه که بر اثر کشیده شدن کله ی مهدی روی سطح زمین خطوطی بین دانشکده ها کشیده شدن.PAP میخواد که تعداد این خطوط رو بشمره تا خفن بودنش رو به همگان آشنا تر کنه (PAP از بیماری خود خفن بینی رنج می بره) اما از اونجایی که باید حواسش به مهدی و اسب ها باشه که در نرن این کار رو به محمدرضا می سپره. ولی محمدرضا که شمردن بلد نیست! اون از همه ی اعداد هم فقط اعداد 0 و 1 رو بلده روی یه سری خط ها عدد 0 و روی یه سری دیگه شون عدد 1 نوشته! اما ازونجایی که محمدرضا مدت خیلی طولانی ای از عمر پوچش رو (تقریبا 12سال) به خوندن یک صفحه از یک کتاب راجع به درخت ها بوده(حتی در تمام دوران تحصیلش و سر تمامی کلاس های دوران قبل دانشگاه،همیشه یه مداد سبز و یه مداد قهوه ای همراهش بود و درخت میکشید)، بعد از کلی کلنجار رفتن با خودش متوجه میشه که این دانشگاه ها و خطوط رسم شده بشدت شبیه به درختن (در نظریه گراف ها البته) و فورا این موضوع رو به اطلاع PAP میرسونه.PAP برای راستی آزمایی حرف محمدرضا و بخاطر اعتماد فوق العاده بالاش به محمدرضا خودش وارد عمل میشه و وقتی میبینه که محمدرضا به طرز عجیبی درست خبر داده، برای اینکه بخاطر شمارش افتضاحش تو ذوقش نزنه(به عنوان تشویق)،تصمیم میگیره که یه بازی براش طراحی کنه که از باقی عمرش لذت ببره.فورا دستورالعمل بازی رو براش توضیح میده: دو نوع دستور وجود داره که PAP میده هر مرحله: 1. اینکه $2$ راس از درخت انتخاب میکنه و به محمدرضا میگه عدد روی تمام یال های مسیر بینشونو از $0$ به $1$ و از $1$ به $0$ تغییر بده. 2. اینکه $2$ راس از درخت انتخاب میکنه و از محمد رضا میخواد مجموع عدد نوشته شده روی یال هاشو بنویسه. اما ازونجایی که محمدرضا تاحالا تو زندگیش هیچی جز درخت ندیده اصلا نمیفهمه که PAP چی میگه! برای همین میخواد که شما با زدن کد این بازی بهش بازیو یاد بدین. # ورودی در خط اول دو عدد $n$ و $q$ تعداد رئوس درخت و تعداد دستورات PAP n, q<=10^5 در $n - 1$ خط بعدی سه عدد $u$ و $v$ و $t$ که نشان دهنده یالی بین $u$ و $v$ با عدد اولیه $t$ است ( $t$ یا $0$ است یا $1$) در $q$ خط بعدی سه عدد $k$ و $u$ و $v$ که اگر $t = 1$ بود یعنی PAP دستور از نوع $1$ برای رئوس $u$ و $v$ داده است و اگر $t = 2$ بود یعنی PAP دستور از نوع $2$ برای رئوس $v$ و $u$ داده است # خروجی به ازای هر دستور از نوع $2$ باید عددی که دستور میخواهد را چاپ کنید # مثال ## ورودی نمونه 4 3 1 2 0 1 3 1 3 4 1 2 1 4 1 2 3 2 1 4 ## خروجی نمونه 2 1 ## توضیح ابتدا در مسیر بین $1$ و $4$ دو یال $1$ وجود دارد پس $2$ چاپ میکند سپس عدد یال های بین $2$ و $3$ تغییر میکنند (یعنی یال بین $1$ و $3$ برابر $0$ میشود و یال بین $1$ و $2$ برابر $1$ میشود) اکنون در مسیر بین $1$ و $4$ تنها یک یال $1$ وجود دارد (یال بین 3 و 4) پس 1 چاپ میکند