آزمایش‌های فوق‌سری «پ.ل.د.» بر روی موضوع جابه‌جایی آنی،‌ انجام می‌شود. طی این آزمایش‌ها، دستگاه جدیدی با $n$ دکمه ساخته شده است که با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند و روی هر یک، مختصات یک نقطه نوشته شده است. با فشردن هر دکمه مکان جسم مورد نظر، نسبت به نقطه‌ی نوشته شده روی آن دکمه قرینه می‌شود. حال پژوهشگران پ.ل.د. می‌خواهند این دستگاه را بر روی موش‌ها آزمایش کنند. این آزمایش شامل $m$ مرحله است. در مرحله‌ی $i$ ام،‌ پژوهشگران یکی از دو عملیات زیر را انجام می‌دهند:

1. نقطه‌ی نوشته شده روی دکمه‌ی $a$ را به $(x, y)$ تغییر می‌دهند.
2. موش را در نقطه‌ی $(x, y)$ قرار می‌دهند و سپس دکمه‌های $a$ تا $b$ (شامل هر دو) را به ترتیب، از کوچک به بزرگ، فشار می‌دهند.

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

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

• $y$ $x$ $a$ 1
• $b$ $a$ $y$ $x$ 2

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

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

• $1 \le n \le 3 \times 10^5$
• $1 \le m \le 10^5$
• $-10^9 \le x, y, u_i, v_i \le 10^9$
• $1 \le a \le b \le n$

در نمونه‌ی ورودی اول دستگاه تنها یک دکمه دارد. در مرحله‌ی اول آزمایش موش ابتدا در نقطه‌ی $(1, 1)$ قرار می‌گیرد و پس از قرینه شدن نسبت به نقطه‌ی نوشته شده روی دکمه‌ی اول یعنی $(0, 0)$ به $(-1, -1)$ منتقل می‌شود. در نتیجه مستطیل مورد نظر مستطیلی است که گوشه‌ی پایین‌چپ آن $(-1, -1)$ و گوشه‌ی بالا‌راست آن $(1, 1)$ است. در مرحله‌ی دوم آزمایش نقطه‌ی نوشته شده روی تنها دکمه‌ی دستگاه به $(1, 1)$ تغییر پیدا می‌کند. در نتیجه در مرحله‌ی سوم چون موش از $(0, 0)$ به $(2, 2)$ منتقل می‌شود، مستطیل مورد نظر،‌ مستطیلی است که گوشه‌ی پایین‌چپ آن $(0, 0)$ و گوشه‌ی بالا‌راست آن $(2, 2)$ است.

• سوال بعد