תיאור

נתבונן ב-$n$ נקודות שלמות במישור, כאשר $n$ מתחלק ב-$3$. קואורדינטות ה-$x$ הן תמורה של המספרים השלמים מ-$1$ עד $n$. גם קואורדינטות ה-$y$ הן תמורה של המספרים השלמים מ-$1$ עד $n$.

בנו תצורה של $n/3$ משולשים שקודקודיהם נמצאים בנקודות הנתונות: כל נקודה חייבת להופיע כקודקוד של אחד המשולשים. המשולשים יכולים להיות מנוונים ויכולים להיחתך באופן חופשי.

הניקוד של תצורה הוא סכום הגדלים של כל המשולשים שבה. הגודל של משולש הוא היקף המלבן החוסם שלו. המלבן החוסם הוא המלבן המינימלי שצלעותיו מקבילות לצירים והוא מכיל את המשולש.

מצאו תצורה המשייגה את הניקוד המרבי האפשרי.

קלט

השורה הראשונה מכילה מספר שלם $n$ ($3 \le n \le 99\,999$; $n$ מתחלק ב-$3$).

כל אחת מ-$n$ השורות הבאות מכילה שני מספרים שלמים $x$ ו-$y$: הקואורדינטות של אחת הנקודות. כל מספר שלם מ-$1$ עד $n$ מופיע פעם אחת בין קואורדינטות ה-$x$ ופעם אחת בין קואורדינטות ה-$y$.

פלט

בשורה הראשונה, הדפיסו את הניקוד המרבי האפשרי.

לאחר מכן, הדפיסו תצורה כלשהי המשייגה ניקוד זה. לשם כך, הדפיסו $n/3$ שורות שבכל אחת מהן שלושה מספרים שלמים: מספרי הנקודות בקלט שהן קודקודיו של משולש. הנקודות ממוספרות מ-$1$ עד $n$ לפי סדר הופעתן בקלט. ניתן להדפיס את המשולשים ואת קודקודיהם בכל סדר.

דוגמה

6
6 5
3 6
5 3
2 4
1 1
4 2

32
2 3 5
6 1 4

הערה