قرر Рамазан الدخول في عمل جاد: زراعة الملفوف.
حقل زراعة الملفوف عبارة عن شبكة لا نهائية من الخلايا. يمكن زراعة رأس واحد من الملفوف في كل خلية.
زرع Рамазан جزءًا فقط من الحقل. خطط لاستخدام عدة مناطق مستطيلة، واتضح أن بعضها قد يتقاطع. تُعد الخلية جزءًا من المزروعات إذا كانت تقع في مستطيل واحد على الأقل.
بصورة رسمية، اختار Рамазан عددًا من المناطق المستطيلة يبلغ $n$، وهي $(x_i^L,y_i^L,x_i^R,y_i^R)$ حيث $x_i^L\le x_i^R$ و$y_i^L\le y_i^R$ و$1\le i\le n$. تحتوي الخلية $(x,y)$ على ملفوف إذا وُجد مستطيل مختار واحد على الأقل $i$، حيث $1\le i\le n$، يحقق $x_i^L\le x\le x_i^R$ و$y_i^L\le y\le y_i^R$.
كان Рамазан في السابق مبرمجًا (وفائزًا أيضًا)، ولذلك قرر استخدام روبوتات مزودة بذكاء اصطناعي لمعالجة المزروعات دوريًا. يستطيع روبوت واحد خدمة أي قطعة أفقية من الخلايا $(x_1^{robot},x_2^{robot},y^{robot})$، أي جميع الخلايا $(x,y)$ التي تحقق $x_1^{robot}\le x\le x_2^{robot}$ و$y=y^{robot}$.
من المهم أن تتحرك الروبوتات على المناطق المزروعة فقط. أدرك أنه لتقليل عدد الروبوتات، من المهم استخدام قطع أفقية لا يمكن توسيعها. سيستخدم Рамазан روبوتًا على قطعة الخلايا $(x_1^{robot},x_2^{robot},y^{robot})$ إذا تحققت الشروط التالية:
- جميع الخلايا $(x,y)$ التي تحقق $x_1^{robot}\le x\le x_2^{robot}$ و$y=y^{robot}$ تنتمي إلى المزروعات.
- الخلية $(x_1^{robot}-1,y^{robot})$ لا تنتمي إلى المزروعات.
- الخلية $(x_2^{robot}+1,y^{robot})$ لا تنتمي إلى المزروعات.
مهمتك هي جمع إحصاءات مهمة عن الروبوتات التي ستعمل في المزرعة. نقول إن الزوج $(x_1,x_2)$ يُخدم في الصف $y$ إذا وُجد روبوت يعمل على القطعة $(x_1,x_2,y)$ بالضبط.
- أوجد جميع الأزواج $(x_1,x_2)$ التي تُخدم في صف ما.
- لكل زوج من هذه الأزواج $(x_1,x_2)$، أوجد عدد الصفوف التي يُخدم فيها.
- لكل زوج من هذه الأزواج $(x_1,x_2)$، أوجد أكبر عدد من الصفوف المتتالية التي يُخدم فيها. وبعبارة أخرى، أوجد أكبر عدد $k$ بحيث يوجد نطاق من $k$ صفوف متتالية $[y_1,y_2]$، حيث $y_2-y_1+1=k$، ويُخدم الزوج $(x_1,x_2)$ في كل صف $y$ يحقق $y_1\le y\le y_2$.
الإدخال
يتكون كل اختبار من عدة حالات اختبار. يحتوي السطر الأول على عدد صحيح واحد $t$ ($1\le t\le 200\,000$)، وهو عدد حالات الاختبار. تليه أوصاف حالات الاختبار.
يحتوي السطر الأول من كل حالة اختبار على عدد صحيح واحد $n$ ($1\le n\le 200\,000$)، وهو عدد المناطق المستطيلة المختارة.
تحتوي الأسطر $n$ التالية على أربعة أعداد صحيحة في كل سطر: $x_i^L,y_i^L,x_i^R,y_i^R$ ($1\le x_i^L\le x_i^R\le 10^9$ و$1\le y_i^L\le y_i^R\le 10^9$)، وهي أوصاف المناطق المستطيلة المختارة.
لنرمز إلى مجموع $n$ في جميع حالات الاختبار ضمن اختبار واحد بالرمز $N$. يُضمن أن $N\le 200\,000$.
الإخراج
لكل حالة اختبار، اطبع أولًا عددًا صحيحًا واحدًا $p$ ($p\ge 1$)، وهو عدد الأزواج $(x_1,x_2)$ التي تُخدم في صف ما.
في الأسطر $p$ التالية، اطبع أربعة أعداد صحيحة في كل سطر: $x_1,x_2,cnt,k$ ($1\le x_1\le x_2\le 10^9$ و$0\le cnt,k\le 10^9$). يجب أن يساوي $cnt$ عدد الصفوف التي يُخدم فيها الزوج $(x_1,x_2)$. ويجب أن يساوي $k$ أكبر عدد من الصفوف المتتالية التي يُخدم فيها الزوج $(x_1,x_2)$.
يجب أن تكون جميع الأزواج $(x_1,x_2)$ مختلفة. يجب طباعة كل زوج يُخدم في صف ما مرة واحدة بالضبط. يمكن طباعة الأزواج بأي ترتيب.
المهام الفرعية
لحالة اختبار، لنرمز إلى عرض الحقل بالرمز $w$، أي $w=\max_{i=1}^{n}x_i^R$، وإلى ارتفاع الحقل بالرمز $h$، أي $h=\max_{i=1}^{n}y_i^R$.
| المهمة الفرعية | النقاط | قيود $n,N$ | قيود $w,h$ | قيود إضافية | المهام الفرعية المطلوبة |
|---|---|---|---|---|---|
| $1$ | $4$ | $n=1$ | |||
| $2$ | $8$ | $h=1$ | |||
| $3$ | $8$ | $n\le 30$, $N\le 3000$ | $w,h\le 10$ | $t\le 100$ | أمثلة |
| $4$ | $4$ | $w,h\le 5000$, $\sum wh\le 25\cdot 10^6$ | أمثلة، $3$ | ||
| $5$ | $8$ | $N\le 3000$ | أمثلة، $3$ | ||
| $6$ | $4$ | $N\le 10000$ | أمثلة، $3,5$ | ||
| $7$ | $8$ | جميع الفترات $[x_i^L,x_i^R]$ تتقاطع | $1$ | ||
| $8$ | $8$ | $y_i^L=1$ | $2$ | ||
| $9$ | $8$ | المستطيلات لا تتقاطع | $1$ | ||
| $10$ | $8$ | لكل $1\le i,j\le n$ ولكل $y\in[y_i^L,y_i^R]\cap[y_j^L,y_j^R]$، يتحقق $[x_i^L,x_i^R]\nsubseteq[x_j^L,x_j^R]$ | $1,9$ | ||
| $11$ | $8$ | كل فترتين من الفترات $[x_i^L,x_i^R+1]$ إما تحتوي إحداهما الأخرى أو لا تتقاطعان | $1$ | ||
| $12$ | $8$ | $N\le 50000$ | أمثلة، $3,5\text{–}6$ | ||
| $13$ | $8$ | $N\le 100000$ | أمثلة، $3,5\text{–}6,12$ | ||
| $14$ | $8$ | $N\le 200000$ | أمثلة، $1\text{–}13$ |
- إذا لم يجد حلك، في أحد الاختبارات، مجموعة الأزواج $(x_1,x_2)$ التي تُخدم في صف ما بصورة صحيحة، فإنه يحصل على حكم «إجابة خاطئة».
إذا كان الحل، في جميع اختبارات المهمة الفرعية والمهام الفرعية المطلوبة، يحقق إحدى الحالات التالية:
- يجد المجموعة بصورة صحيحة، لكن ليست كل قيم $cnt$ صحيحة، فإنه يحصل على $50\%$ من نقاط المهمة الفرعية.
- يجد المجموعة وجميع قيم $cnt$ بصورة صحيحة، لكن ليست كل قيم $k$ صحيحة، فإنه يحصل على $75\%$ من نقاط المهمة الفرعية.
- يجد المجموعة وجميع قيم $cnt$ وجميع قيم $k$ بصورة صحيحة، فإنه يحصل على $100\%$ من نقاط المهمة الفرعية.
لاحظ أنه للحصول على نقاط جزئية للمهمة الفرعية، لا يزال عليك طباعة قيم ما لـ$cnt$ و$k$ لكل زوج $(x_1,x_2)$، لكن لا يلزم أن تكون صحيحة.
أمثلة
الإدخال 1
4 2 2 2 3 3 3 3 4 4 2 2 1 2 3 1 2 3 2 4 2 2 4 5 3 4 9 7 2 9 9 10 7 1 9 7 7 2 1 2 9 5 1 6 8 4 5 7 6 1 8 4 10 1 6 3 6 1 2 7 3 4 1 7 1
الإخراج 1
3 2 3 1 1 2 4 1 1 3 4 1 1 2 1 3 1 1 2 2 2 1 4 2 4 2 2 2 9 4 2 3 9 2 2 7 9 3 3 6 1 4 2 2 1 6 1 1 1 7 3 2 2 2 4 2 4 7 2 1 5 6 2 1
ملاحظة
حالتا الاختبار الأولى والثانية في اختبار المثال الوارد في نص المسألة.
في حالة الاختبار الأولى، ستُستخدم روبوتات على القطع $(2,3,2)$ و$(2,4,3)$ و$(3,4,4)$. وبالتالي، تُخدم الأزواج $(2,3)$ و$(2,4)$ و$(3,4)$ في صف ما، ويُخدم كل منها في صف واحد بالضبط.
في حالة الاختبار الثانية، ستُستخدم روبوتات على القطع $(2,2,1)$ و$(2,4,2)$ و$(2,2,3)$. وبالتالي، يُخدم الزوجان $(2,2)$ و$(2,4)$ في صف ما. يُخدم الزوج $(2,2)$ في الصفين $1,3$، ويُخدم الزوج $(2,4)$ في الصف $2$.
حالتا الاختبار الثالثة والرابعة في اختبار المثال الوارد في نص المسألة.