本题与 #707. 【UER #10】重构元宇宙 的差异仅有数据范围与 query 函数的返回值类型。

这是一道交互题。

在表彰大会上，码王 skip 蚤分享起了他最得意的一次用代码拯救世界的经历，只不过这个世界是虚拟世界。

跳蚤国有一个自主研发的元宇宙平台 —— 蚤宇宙。虽然现实世界只有三维，但在蚤宇宙，你可以体验到 $k$ 维空间的极致体验！

蚤宇宙里面共有 $n$ 个物体，编号为 $0$ 到 $n-1$，其中每个物体的位置可以用一个 $k$ 维空间中的坐标表示。

然而在一个雨夜，一道闪电划破夜空，劈到了位于跳蚤利亚的蚤宇宙核心数据中心，引发了一场大火，无数的蚤宇宙数据化为焦土。

所幸在一个蚤宇宙数据备份中心里恰巧存储了这 $n$ 个物体两两之间的欧几里得距离。即，如果有两个物体的位置分别为 $(x_0,x_1,\dots ,x_{k-1})\in {\mathbb{R}}^k$ 和 $(x_0^{\prime },x_1^{\prime },\dots ,x_{k-1}^{\prime })\in {\mathbb{R}}^k$，那么它们之间的距离就是 $d(x,x^{\prime })=\sqrt{\sum _{i=0}^{k-1}(x_i-x_i^{\prime }{)}^2}$。

“没有人比我更懂怎么重构元宇宙”，码王激动地说道。那晚，码王通过这些数据，还原出了一组合法的物体坐标，成为了蚤宇宙的英雄。虽然和原坐标不一定一样，但他们两两之间点的距离与备份中心里的记录完全一致。

坐在台下的你想要挑战码王！你不仅想解决相同的问题，还想只使用一部分备份中心存储的距离数据，来达到相同的目的。

任务

本题仅支持符合 C++ 11 标准及以上的 C++ 语言。

你必须引用 distance.h。

你需要实现下面的过程：

std::vector<std::vector<double>> solve(int n, int k, int lim);

这个过程会被恰好调用一次。

$n$ 表示点的个数（即物体的个数），$k$ 表示空间维数，$\lim$ 表示你能使用 query 次数的上限。

你需要返回一个长度为 $n$ 的数组，元素是一个长度为 $k$ 的实数向量，表示每个点的坐标。

你可以调用以下函数：

double query(int a, int b);

你需要保证 $a,b\in [0,n)$。

这个函数会返回 $a$ 号点和 $b$ 号点欧几里得距离的平方。

具体地，设 $a$ 号点坐标为 $(x_0,x_1,\dots ,x_{k-1})$，$b$ 号点坐标为 $(x_0^{\prime },x_1^{\prime },\dots ,x_{k-1}^{\prime })$，则函数会返回：$d(x,x^{\prime }{)}^2=\sum _{i=0}^{k-1}{(x_i-x_i^{\prime })}^2$。

这个函数至多被调用 $\lim$ 次。

评测方式

设 $D^2$ 为原始数据点中每一维坐标的极差的平方和，若对于任意 $i,j\in [0,n)$，返回的 $i$ 号点和 $j$ 号点欧几里得距离为 $\mathrm{out}$，输入的 $i$ 号点和 $j$ 号点距离为 $\mathrm{ans}$，均有 $\frac{|\mathrm{out}-\mathrm{ans}|}{max\{1,D\}}\le {10}^{-6}$，则你的返回结果将被判定为正确。

样例评测库将读入如下格式的输入数据：

第一行三个整数 $n,k,\lim$。

接下来 $n$ 行，每行 $k$ 个实数表示点的坐标。

样例评测库将输出如下格式的输出数据：

如果你的返回结果错误或交互过程不合法，则评测库会输出 WA 并输出错误原因。

否则输出两行，第一行为 OK，第二行输出你使用 query 的次数。

交互式类型的题目怎么本地测试

最终测试中，点坐标是确定的，不会因为你的询问而改变，并且最终评测库与下发评测库仅有反作弊上的差别。

样例一

input

3 2 9
0 0
0 1
1 0

output

OK
query count: 9

explanation

你可以询问出所有点对间的距离。

query 的返回值如下

合法的返回值并不唯一，一组合法的返回是：$(1,1),(0,1),(1,0)$。

样例二

见附件下载中的 ex_distance2.in 和 ex_distance2.ans。

数据范围与提示

对于所有数据，保证 $1\le k\le n\le 500,n(k+1)\le \lim \le 250500$，点的坐标均为 $[-500,500]$ 内的实数。

保证合法的交互过程中，交互库不会使用超过 $\mathtt{\text{0.5s}}$ 的时间和 $\mathtt{\text{64MB}}$ 的空间。

hack

hack 数据的格式与样例输入数据一致，实数的小数部分不得超过 $10$ 位。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$