Bạn có một tập hợp các miền tam giác lát kín một mặt phẳng hai chiều vô hạn. Cách lát được định nghĩa như sau (xem hình minh họa để hiểu rõ hơn):

• Nhắc lại rằng công thức Euler phát biểu \(e^{ix}=\cos(x)+i\sin(x)\) với \(x\) thực. Trước tiên, với mọi số nguyên \(x,y\), vẽ một đỉnh tại \(x+y\exp(\pi i/3)\) trên mặt phẳng phức.
• Sau đó, với mỗi bộ ba đỉnh ở bước trên tạo thành một tam giác đều có độ dài cạnh bằng \(1\), vẽ các cạnh tạo nên đường biên của tam giác. Ngoài ra, vẽ một đỉnh tại tâm tam giác và các cạnh nối tâm tam giác với từng đỉnh trong ba đỉnh ngoài.

Bạn được cho \(N\) (\(2\le N\le 2\cdot 10^5\)) điểm đầu vào, mỗi điểm nằm hoàn toàn bên trong một miền nào đó (tức là không nằm trên bất kỳ đỉnh hay cạnh nào). Với mỗi cặp điểm đầu vào, định nghĩa khoảng cách giữa chúng là số cạnh ít nhất bị cắt qua khi vẽ một đường đi từ điểm này đến điểm kia mà không đi qua bất kỳ đỉnh nào.

Hãy in tổng khoảng cách của tất cả \(N(N-1)/2\) cặp điểm đầu vào.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(T\ge 1\)), là số bộ kiểm thử độc lập. Mỗi bộ kiểm thử được mô tả như sau:

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x\), \(y\) và \(z\) (\(0\le x,y<10^6\), \(0\le z<12\)), biểu diễn một điểm tại \(x+y\exp(\pi i/3)+\epsilon\cdot\exp((1+2z)\pi i/12)\) trên mặt phẳng phức (trong đó \(\epsilon\) là một số dương nhỏ).

Đảm bảo rằng tổng \(N\) trên tất cả các bộ kiểm thử không vượt quá \(2\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ kiểm thử, in trên một dòng mới tổng khoảng cách của tất cả \(N(N-1)/2\) cặp điểm.

Ví dụ

6
2
0 0 0
0 0 0
2
0 0 0
1 1 7
2
0 0 0
0 0 6
3
0 0 1
0 0 5
0 0 9
2
0 2 11
1 1 1
2
2 0 11
1 1 1

0
3
6
12
2
6

Phân nhóm

• Dữ liệu 2–5: \(N\le 10\), \(0\le x,y<5\).
• Dữ liệu 6–13: \(N\le 10\).
• Dữ liệu 14–21: \(T=1\).

Nguồn

USACO 2026 Contest 3, Platinum — “All Pairs Shortest Paths” — tác giả: Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1596