Những chú bò đang làm một bài thi trắc nghiệm. Nhưng thay vì một bài thi thông thường, nơi các lựa chọn của bạn được chấm riêng cho từng câu rồi cộng lại, trong bài thi này các lựa chọn được cộng lại trước khi chấm điểm.

Cụ thể, bạn được cho \(N\) (\(2\le N\le 10^5\)) nhóm vectơ nguyên trên mặt phẳng 2D, trong đó mỗi vectơ được biểu diễn bằng một cặp có thứ tự \((x,y)\). Hãy chọn một vectơ từ mỗi nhóm sao cho tổng các vectơ cách gốc tọa độ xa nhất có thể.

Đảm bảo tổng số vectơ không vượt quá \(2\cdot 10^5\). Mỗi nhóm có ít nhất \(2\) vectơ, và trong một nhóm, mọi vectơ đều khác nhau. Đồng thời, giá trị tuyệt đối của mọi tọa độ \(x\) và \(y\) không vượt quá \(\frac{10^9}{N}\).

Dữ liệu vào

Dòng đầu chứa \(N\), là số nhóm.

Mỗi nhóm bắt đầu bằng \(G\), là số vectơ trong nhóm, tiếp theo là \(G\) dòng chứa các vectơ của nhóm đó. Các nhóm liên tiếp được ngăn cách bởi dòng trống.

Dữ liệu ra

In bình phương khoảng cách Euclid lớn nhất có thể.

Phân nhóm

• Trong các test 1–5, tổng số vectơ không vượt quá \(10^3\).
• Trong các test 6–9, mỗi nhóm có đúng hai vectơ.
• Các test 10–17 không có ràng buộc bổ sung.

Ví dụ

3

2
-2 0
1 0

2
0 -2
0 1

3
-5 -5
5 1
10 10

242

Nguồn

USACO 2022 January Contest, Platinum — Multiple Choice Test: https://usaco.org/index.php?page=viewproblem2&cpid=1190

Tác giả: Benjamin Qi.