لديك $N$ نقاط مختلفة في المستوى ثنائي الأبعاد، مرقمة من $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$ لهما نفس اللون، لذا فهو غير صالح.
في المثال الثاني، يوجد رباعي أضلاع صالح، لكن لا يوجد أي رباعي أضلاع محدب يحقق المتطلبات.
في المثال الثالث، لا يمكن تكوين أي رباعي أضلاع صالح.
كما هو موضح في المثال الرابع، يمكن أن تكون الإجابة كبيرة جداً.