• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

آزمایش‌های فوق سری «پ.ل.د» بر روی موضوع جابه‌جایی آنی، انجام می‌شود. طی این آزمایش‌ها، دستگاه جدیدی با \(n\) دکمه ساخته شده است که با اعداد ۱ تا \(n\) شماره‌گذاری شده‌اند و روی هر یک ، مختصات یک نقطه نوشته شده است. با فشردن هر دکمه مکان جسم مورد نظر ، نسبت به نقطه‌ي نوشته بشده روی آن دکمه قرینه می‌شود. حال پژوهشگران پ.ل.د می‌خواهند این دستگاه را بر روی موش‌ها آزمایش کنند. این آزمایش شامل \(m\) مرحله است. در مرحله‌ی \(i\)ام پژوهشگران یکی از دو عملیات زیر را انجام می‌دهند: ۱. نقطه‌ي نوشته شده روی دکمه‌ي \(a\) را به \((x,y)\) تغییر می‌دهند. ۲. موش را در نقطه‌ي \((x,y)\) قرار می‌دهند و سپس دکمه‌های \(a\) تا \(b\) (شامل هر دو) را به ترتیب، از کوچک به بزرگ ، فشار می‌دهند.

پژوهشگران می‌خواهند مطمئن شوند که موش در طی هر یک از عملیات‌های نوع دوم، از محوطه‌ی آزمایشگاه خارج نشود. در نتیجه به ازای هر یک از عملیات‌ها، آن‌ها می‌خواهند کوچک‌ترین مستطیلی را پیدا کنند که اضلاعش موازی محورهای مختصات است و موش در تمام لحظه‌های عملیات‌ها، داخل و یا روی محیط آن باشد. برنامه‌ای بنویسید که خواسته‌ی پژوهشگران را برآورده کند.

ورودی

در خط اول ورودی، عدد \(n\)، تعداد دکمه‌های دستگاه آمده است. در هر یک از \(n\) خط بعدی دو عدد \(u\) و \(v\) آمده است که نشان می‌دهد در ابتدا نقطه‌ی \((u,v)\) روی دکمه‌ی \(i\)ام نوشته شده است. در خط \(n+2\) ام عدد \(m\)، تعداد مراحل آزمایش آمده است. در هر یک از \(m\) خط بعدی توضیحات مربوط به یک مرحله از آزمایش آمده است. عد اول هر خط نوع عملیات انجام شده در آن مرحله را مشخص می‌کند که برابر با یک یا دو است و پس از آن اعداد مربوط به آن نوع عملیات آمده‌اند. در نتیجه هر یک از این \(m\) خط به یکی 4از دو صورت زیر هستند:

• \(1 \, a\, x\, y\)
• \(2\, x\, y\, a\, b\)

\[1 \leq n \leq 300\ 000\] \[ 1 \leq m \leq 100\ 000\] \[ -10^9 \leq x,y,u_i,v_i \leq 10^9 \] \[1 \leq a \leq b \leq n\]

خروجی

به ازای هر یک از مراحل آزمایش که در آن عملیات نوع دوم انجام شده است، چهار عدد \(x_1\) و \(y_1\) و \(x_2\) و \(y_2\) را بنویسید طوری که نقاط \((x_1,y_1)\) و \((x_2,y_2)\) به ترتیب گوشه‌ی پایین چپ و بالا راست مستطیل موردنظر پژوهشگران برای آن مرحله از آزمایش باشد.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۲	فقط عملیات نوع دوم انجام می‌شود و \( n \le 2000\)
۲	۲۳	در عملیات های نوع دوم فقط دکمه ها فشرده می‌شود.(\( a = 1\) و \(b = n\))
۳	۶۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

1
0 0
3
2 1 1 1 1
1 1 1 1
2 0 0 1 1

خروجی نمونه ۱

-1 -1 1 1
0 0 2 2

ورودی نمونه ۲

4
0 0
0 1
1 0
1 1
3
2 1 3 2 4
1 3 2 3
2 9 2 1 4

خروجی نمونه ۲

-1 -1 3 3
-9 -2 9 4

۲۵امین دوره المپیاد کامپیوتر - آزمون نهایی اول - ۱۳۹۴/۶/۱۸