题目描述

CDN 分发服务器是内容运营平台的关键设施。按业务设计，用户通常从距离自己最近的 CDN 节点下载内容。选址时需要同时考虑覆盖用户规模与空间距离，使全体用户到所属 CDN 的加权总距离尽可能小。

现有 $p$ 座城市，已知每座城市的坐标与用户数，以及预算允许建设的 CDN 台数 $q$。请按 k-means 流程求出各 CDN 的选址坐标及其覆盖用户数。

计算须遵守：

• 开始时地图上尚未部署任何 CDN；
• CDN 必须落在某一座城市上；
• 迭代开始时，将前 $q$ 座城市作为初始选址；
• 当各 CDN 所在城市不再变化时结束迭代；
• 若某座城市到多台 CDN 的距离同为最短，则归属序号更靠前的那一台。

公式说明

一名用户到某台 CDN 的距离为

其中城市坐标为 $(x,y)$，CDN 坐标为 $(c_x,c_y)$。

全体用户的加权总距离为

其中第 $i$ 座城市坐标为 $(x_i,y_i)$、用户数为 $u_i$，$z_i$ 是距离该城市最近的 CDN 编号，$(c_{x,z_i}, c_{y,z_i})$ 为该 CDN 的坐标。

簇内更新选址时，在当前簇包含的城市中选出一座，使簇内全部用户到该城市的加权距离之和最小；若有多座城市同为最优，取原输入中序号更靠前的一座。

输入描述

1. 第 $1$ 行：正整数 $p$，表示城市数目，取值范围 $(0,100)$。
2. 第 $2$ 行至第 $p+1$ 行：每行格式为 $a,b,c$，其中 $a,b$ 为该城市横、纵坐标，$c$ 为用户数（单位：万人）。$a$、$b$、$c$ 均为保留 $2$ 位小数的浮点数，取值范围 $(0,100)$。
3. 第 $p+2$ 行：正整数 $q$，表示预算可支持的 CDN 数目，满足 $q \le p$，取值范围 $(0,100)$。

输出描述

第 $1$ 行至第 $q$ 行：每行格式为 $a,b,c$，表示该 CDN 的横、纵坐标，以及它覆盖的用户数（单位：万人）。$a$、$b$、$c$ 均为保留 $2$ 位小数的浮点数，取值范围 $(0,100)$。

CDN 按 $a$ 升序输出；$a$ 相同时按 $b$ 升序输出。

样例1

输入

3
0.00,0.00,2.00
3.00,4.00,5.00
8.00,0.00,3.00
1

输出

3.00,4.00,10.00

说明

$q=1$，三座城市同属一簇。各城市两两距离分别为 $5$、$8$、$\sqrt{41}$。以 $(0.00,0.00)$ 为中心时加权总距离为 $49$；以 $(3.00,4.00)$ 为中心时约为 $29.21$；以 $(8.00,0.00)$ 为中心时约为 $48.02$。因此唯一最优选址为 $(3.00,4.00)$，覆盖用户 $2.00+5.00+3.00=10.00$。

样例2

输入

4
0.00,0.00,1.50
2.00,2.00,2.50
8.00,8.00,1.50
10.00,10.00,3.50
2

输出

2.00,2.00,4.00
10.00,10.00,5.00

说明

四座城市坐标为 $(0.00,0.00)$、$(2.00,2.00)$、$(8.00,8.00)$、$(10.00,10.00)$。迭代开始时，初始 CDN 设在前两座城市 $(0.00,0.00)$ 与 $(2.00,2.00)$。后两座城市均更靠近第二台 CDN，于是分成两簇：第一簇仅含首座城市，第二簇含其余三座。第二簇内重新选址后 CDN 移到 $(8.00,8.00)$。再次按最近 CDN 分组，得到 $\{(0.00,0.00),(2.00,2.00)\}$ 与 $\{(8.00,8.00),(10.00,10.00)\}$ 两簇，簇内最优城市分别为 $(2.00,2.00)$ 与 $(10.00,10.00)$。此后分组不再变化，迭代结束。覆盖用户分别为 $1.50+2.50=4.00$ 与 $1.50+3.50=5.00$。