Рамазан החליט לעסוק בעסק רציני — גידול כרוב.

השדה לגידול הכרוב הוא שדה משבצות אינסופי. בכל משבצת בשדה אפשר לשתול ראש כרוב אחד.

Рамазан שתל רק בחלק מהשדה. הוא תכנן להשתמש בכמה חלקות מלבניות, והתברר שחלקן עשויות לחפוף. משבצת שייכת לשטח השתול אם היא נמצאת לפחות באחד המלבנים.

באופן פורמלי, Рамазан בחר $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$), כך שבכל שורה $y_1\le y\le y_2$ הזוג $(x_1,x_2)$ מטופל בשורה $y$.

קלט

כל מבחן מורכב מכמה מקרי בדיקה. בשורה הראשונה נתון מספר שלם אחד $t$ ($1\le t\le200\,000$), מספר מקרי הבדיקה. לאחר מכן מופיעים תיאורי מקרי הבדיקה.

בשורה הראשונה של כל מקרה בדיקה נתון מספר שלם אחד $n$ ($1\le n\le200\,000$), מספר החלקות המלבניות שנבחרו.

בכל אחת מ-$n$ השורות הבאות נתונים ארבעה מספרים שלמים $x_i^L,y_i^L,x_i^R,y_i^R$ ($1\le x_i^L\le x_i^R\le10^9$, $1\le y_i^L\le y_i^R\le10^9$), המתארים את החלקות המלבניות שנבחרו.

נסמן ב-$N$ את סכום ערכי $n$ בכל מקרי הבדיקה במבחן אחד. מובטח כי $N\le200\,000$.

פלט

לכל מקרה בדיקה, הדפיסו תחילה מספר שלם אחד $p$ ($p\ge1$), מספר הזוגות $(x_1,x_2)$ שמטופלים בשורה כלשהי.

בכל אחת מ-$p$ השורות הבאות הדפיסו ארבעה מספרים שלמים $x_1,x_2,cnt,k$ ($1\le x_1\le x_2\le10^9$, $0\le cnt,k\le10^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$.

• אם במבחן מסוים הפתרון שלכם מוצא באופן שגוי את קבוצת הזוגות $(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$.

מקרי הבדיקה השלישי והרביעי במבחן שבדוגמה שבשאלה.