กำหนดจุดที่แตกต่างกัน $N$ จุดบนระนาบ 2 มิติ โดยมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N$ พิกัดของจุดที่ $i$ คือ $(x_i, y_i)$
แต่ละจุดมีสี โดยมีสีทั้งหมด $N$ สี ซึ่งมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N$ และจุดที่ $i$ มีสีเป็น $c_i$
งานของคุณคือเลือกจุดสี่จุดที่มีสีแตกต่างกันเป็นคู่ๆ แล้วเชื่อมจุดเหล่านั้นตามลำดับใดก็ได้เพื่อสร้างเป็นรูปสี่เหลี่ยม รูปสี่เหลี่ยมนี้สามารถมีมุมภายในเท่ากับ $180^\circ$ พอดีได้ แต่ต้องไม่มีด้านสองด้านที่ไม่ติดกันคู่ใดตัดกัน
จงตรวจสอบว่าสามารถสร้างรูปสี่เหลี่ยมดังกล่าวได้หรือไม่ หากสร้างได้ ให้ $S$ เป็นพื้นที่ที่มากที่สุดที่เป็นไปได้จากรูปสี่เหลี่ยมที่ถูกต้องทั้งหมด แล้วแสดงผลค่า $2S$ เป็นจำนวนเต็ม หากไม่สามารถสร้างได้ ให้แสดงผล $0$
มีชุดทดสอบที่เป็นอิสระต่อกัน $T$ ชุด
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะกำหนดให้ในรูปแบบต่อไปนี้:
T case1 case2 : caseT
ในที่นี้ แต่ละ $\text{case}_i$ จะกำหนดให้ในรูปแบบต่อไปนี้:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $1 \le T \le 10^4$
- $4 \le N \le 10^5$
- $|x_i|, |y_i| \le 10^8$
- $1 \le c_i \le N$
- ถ้า $i \neq j$ แล้ว $(x_i, y_i) \neq (x_j, y_j)$
- ผลรวมของ $N$ จากทุกชุดทดสอบจะไม่เกิน $10^5$
ข้อมูลส่งออก
สำหรับแต่ละชุดทดสอบ ให้แสดงคำตอบในบรรทัดของตัวเอง
ตัวอย่าง
ข้อมูลนำเข้าตัวอย่าง 1
4 6 2 4 1 5 4 2 6 2 3 5 1 1 2 1 2 1 3 4 4 1 1 1 3 5 2 7 2 3 4 3 4 5 0 0 1 0 1 2 1 0 2 0 2 3 2 0 3 4 0 0 1 0 100000000 2 100000000 0 3 100000000 100000000 4
ข้อมูลส่งออกตัวอย่าง 1
15 17 0 20000000000000000
หมายเหตุ
ในตัวอย่างแรก การเชื่อมจุด $1, 2, 3, 6$ ตามลำดับนี้จะสร้างรูปสี่เหลี่ยมที่ถูกต้องซึ่งมีพื้นที่ $15/2$ ซึ่งเป็นค่ามากที่สุดในบรรดาทางเลือกที่ถูกต้องทั้งหมด รูปสี่เหลี่ยมที่สร้างจากจุด $1, 2, 4, 5$ มีพื้นที่ $9$ แต่จุดที่ $1$ และจุดที่ $4$ มีสีเดียวกัน จึงไม่ถูกต้อง
ในตัวอย่างที่สอง มีรูปสี่เหลี่ยมที่ถูกต้องอยู่ แต่ไม่มีรูปสี่เหลี่ยมมุมนูนใดที่ตรงตามข้อกำหนด
ในตัวอย่างที่สาม ไม่สามารถสร้างรูปสี่เหลี่ยมที่ถูกต้องได้เลย
ดังที่แสดงในตัวอย่างที่สี่ คำตอบอาจมีค่าใหญ่มากได้