คำอธิบาย

พิจารณาจุดพิกัดจำนวนเต็ม $n$ จุดบนระนาบ โดยที่ $n$ หารด้วย $3$ ลงตัว พิกัด $x$ เป็นการเรียงสับเปลี่ยนของจำนวนเต็มตั้งแต่ $1$ ถึง $n$ พิกัด $y$ ก็เป็นการเรียงสับเปลี่ยนของจำนวนเต็มตั้งแต่ $1$ ถึง $n$ เช่นกัน

จงสร้างการจัดวางของรูปสามเหลี่ยมจำนวน $n/3$ รูปที่มีจุดยอดอยู่ในจุดที่กำหนดให้ โดยแต่ละจุดต้องปรากฏเป็นจุดยอดของรูปสามเหลี่ยมรูปใดรูปหนึ่ง รูปสามเหลี่ยมสามารถเป็นรูปสามเหลี่ยมลดรูปได้และสามารถตัดกันได้อย่างอิสระ

คะแนนของการจัดวางคือผลรวมของขนาดของรูปสามเหลี่ยมทั้งหมดในการจัดวางนั้น ขนาดของรูปสามเหลี่ยมคือความยาวรอบรูปของรูปสี่เหลี่ยมมุมฉากล้อมรอบ (bounding rectangle) ของมัน รูปสี่เหลี่ยมมุมฉากล้อมรอบคือรูปสี่เหลี่ยมมุมฉากที่เล็กที่สุดที่มีด้านขนานกับแกนพิกัดและบรรจุรูปสามเหลี่ยมนั้นไว้ภายใน

จงหาการจัดวางที่ได้คะแนนมากที่สุดเท่าที่เป็นไปได้

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $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

หมายเหตุ