"""import sys
from sklearn.cluster import KMeans
import numpy as np
import numba
from numba import njit, b1, i1, i4, i8, f8
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
@njit
def minimum_enclosing_disc(XY):
EPS = 1e-9
X = XY[:, 0]
Y = XY[:, 1]
Z = X + Y * 1j
N = len(Z)
P = np.arange(N)
np.random.shuffle(P)
Z = Z[P]
if N == 0:
return (0.0 + 0.0j, 0.0)
if N == 1:
return (Z[0], 0.0)
def make_circle_3(a, b, c):
A, B = b - a, c - a
z = A * A.conjugate() * B - A * B * B.conjugate()
z /= A.conjugate() * B - A * B.conjugate()
return z + a, abs(z)
def make_circle_2(a, b):
z = (a + b) / 2
return z, abs(z - a)
def in_circle(a, circle):
z, r = circle
return abs(a - z) <= r + EPS
c = make_circle_2(Z[0], Z[1])
for i in range(2, N):
if in_circle(Z[i], c):
continue
c = make_circle_2(Z[0], Z[i])
for j in range(1, i):
if in_circle(Z[j], c):
continue
c = make_circle_2(Z[i], Z[j])
for k in range(j):
if in_circle(Z[k], c):
continue
c = make_circle_3(Z[i], Z[j], Z[k])
return c
@njit
def minimum_enclosing_disc_int(XY):
N = len(XY)
if N == 0:
return 0, 0, 0
MAX = 10**6
c, r = minimum_enclosing_disc(XY)
best_x = best_y = 0
best_energy = 1 << 60
for x in range(int(c.real), int(c.real) + 2):
if not 0 <= x < MAX:
continue
for y in range(int(c.imag), int(c.imag) + 2):
if not 0 <= y < MAX:
continue
DX = XY[:, 0] - x
DY = XY[:, 1] - y
energy = np.max(DX * DX + DY * DY)
if best_energy > energy:
best_energy = energy
best_x, best_y = x, y
return best_x, best_y, best_energy
def init_state(problem):
N, K, AB = problem
km = KMeans(n_clusters=K)
km.fit(AB)
label = km.labels_
problem = (N, K, AB)
clust = label
center = np.empty((K, 2), np.int64)
energy = np.empty(K, np.int64)
for k in range(K):
XY = AB[np.where(clust == k)]
x, y, e = minimum_enclosing_disc_int(XY)
center[k] = (x, y)
energy[k] = e
state = (clust, center, energy)
score = energy.sum()
return state, score
@njit
def move(problem, state, score, param):
N, K, AB = problem
clust, center, energy = state
v, to_k = param
frm_k = clust[v]
change_log = (clust.copy(), center.copy(), energy.copy(), score)
clust[v] = to_k
for i in range(2):
if i == 0:
k = frm_k
else:
k = to_k
XY = AB[clust == k]
x, y, e = minimum_enclosing_disc_int(XY)
center[k] = (x, y)
energy[k] = e
new_state = (clust, center, energy)
new_score = energy.sum()
return new_state, new_score, change_log
@njit
def rollback(problem, state, score, change_log):
clust, center, energy, score = change_log
return (clust, center, energy), score
@njit
def mountain(problem, state, score, max_step):
N, K, AB = problem
clust, center, energy = state
def random_param():
while True:
v = np.random.randint(0, N)
k = clust[v]
a, b = AB[v]
cx, cy = center[k]
if (a - cx)**2 + (b - cy)**2 != energy[k]:
continue
break
to_k = np.random.randint(0, K)
return (v, to_k)
for step in range(max_step):
param = random_param()
before_score = score
state, score, change_log = move(problem, state, score, param)
if before_score < score:
state, score = rollback(problem, state, score, change_log)
return state, score
def output(problem, state, file=None):
if file:
FILE = open(file, 'w')
N, K, AB = problem
clust, center, energy = state
for k in range(K):
print(center[k][0], center[k][1], energy[k]) #, file=FILE)
def plot(problem, state):
N, K, AB = problem
clust, center, energy = state
from matplotlib import pyplot as plt, patches
plt.figure()
ax = plt.axes()
for k in range(K):
c = patches.Circle(xy=tuple(center[k]),
radius=energy[k]**.5,
fill=False)
ax.add_patch(c)
XY = AB[clust == k]
plt.scatter(XY[:, 0], XY[:, 1])
plt.show()
def main(file=None):
if file:
FILE = open(file)
else:
FILE = sys.stdin
N, K = map(int, FILE.readline().split())
AB = np.array(FILE.read().split(), np.int64).reshape(N, 2)
P = np.arange(N)
np.random.shuffle(P)
AB = AB[P]
problem = (N, K, AB)
best_score = 1 << 60
state, score = init_state(problem)
state, score = mountain(problem, state, score, 10000)
# plot(problem, state)
# fname = file + f'_{score}.txt'
output(problem, state)
main()"""
print("""83376 922605 11662383850
807856 299177 8597555801
71999 84946 6186144553
845660 890684 14242667920
330505 470048 10322790682
747790 126430 9288365237
335754 888860 6274079874
418749 317614 11258887841
593264 461202 13191782882
589177 873384 14640232210
948697 163709 15127845674
101030 395439 6267543890
301495 108627 11749281757
772096 659454 12332039245
933003 489925 11349047770
142194 251488 13878393941
469054 711038 10610512985
232674 738980 8814013045
92952 655771 17094120601
564316 102239 12188776840""")