406972: GYM102640 A Points coloring

You are given $$$n$$$ points on a plane. All points are pairwise distinct. You have to paint each point in one of $$$k$$$ colors so that there are exactly $$$\frac{n}{k}$$$ points of each color. It is guaranteed that $$$k$$$ is a divisor of $$$n$$$.

For each color $$$c$$$ the value $$$s_c$$$ — the square distance between the two closest points of this color — is calculated. The total score is a sum of $$$s_c$$$. You have to maximize your total score.

The first line contains an integer $$$t$$$ — the number of tests.

Each test starts with two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$1 \le k \le 25$$$) — the numbers of points and colors. Then $$$n$$$ lines follow, each of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 1000$$$) — the coordinates of points.

For each test output "Case #j:", where $$$j$$$ is the test number from $$$1$$$ to $$$t$$$, and then a string of $$$n$$$ uppercase Latin letters, whose $$$i$$$-th letter is a color to paint the $$$i$$$-th point. Each letter should be among $$$k$$$ first letters of the alphabet.

2
4 2
0 0
1 0
1 1
0 1
4 2
0 0
1 0
1 1
0 1

Case #1: AABB
Case #2: ABAB

The sample has two identical test cases but with different answers. The painting "AABB" gives score 2, and the painting "ABAB" gives score 4.

The test file has 60 test cases. Tests 1-10 have some unique feature, tests 11-20 — another feature, tests 21-30 — the third feature, tests 31-40 — the fourth feature, and tests 41-60 are randomly generated.

The total score is the average score for all test cases, rounded down. If the test file contained only two sample test cases, the total score would be 3.