注：如果此前已经有人发了此做法的博客，请告诉我，我会把这条博客设为仅自己可见。

由于数据随机，本解法默认不会出现两个点的位置相同。如果相同的话本解法也能做，但是在代码上可能会多一些特判之类的。

本题解下标默认均从 $1$ 开始，与原题不一样，请注意。

首先，在 $k$ 位空间里，我们只需要知道一个点到 $k+1$ 个已知点的距离，就可以确定这个点的位置了。也就是说，我们只需要确定好 $k+1$ 个点之间的距离，并对于每个点都问它和那 $k+1$ 个点之间的距离就可以了。这需要的询问次数显然是小于等于 $n(k+1)$ 的，所以猜测这个做法就是对的。但是，如果我们直接去解，会发现我们要解一些 $k+1$ 元二次方程组，而这是我们不会的。

不过没关系，我们仍然可以尝试一个一个把点加进来。对于第一个点，我们直接让它的坐标为 $(0,0,\cdots,0)$，因为这样比较方便后续的计算。对于第二个点，可以令 $x_{2,1}=\operatorname{query}(1,2)=l_1$，其余维度均为 $0$。对于第三个点，考虑类似的让其除了前两个维度外的坐标均为 $0$，设 $\operatorname{query}(1,3)=l_2,\operatorname{query}(2,3)=l_3$，则有

$$ \begin{cases} x_{3,1}^2+x_{3,2}^2=l_2\\ (x_{3,1}-x_{2,1})^2+x_{3,2}^2=l_3 \end{cases} $$

这时我们规定第 $x$ 个点除了前 $x-1$ 维的好处就体现出来了：现在两个式子的 $x_{3,2}^2$ 是重复的，直接相减，得到

$$ \begin{aligned} (x_{3,1}-x_{2,1})^2-x_{3,1}^2&=l_3-l_2\\ (x_{3,1}-x_{2,1}+x_{3,1})(x_{3,1}-x_{2,1}-x_{3,1})&=l_3-l_2\\ 2x_{3,1}-x_{2,1}&=-\frac{l_3-l_2}{x_{2,1}}\\ x_{3,1}&=\frac{x_{2,1}}{2}-\frac{l_3-l_2}{2x_{2,1}} \end{aligned} $$

解出 $x_{3,1}$ 之后，直接带入即可得到 $x_{3,2}$ 的两个解，任取其中一个即可。对于第四个点，也是类似的：

$$ \begin{cases} x_{4,1}^2+x_{4,2}^2+x_{4,3}^2=l_4\\ (x_{4,1}-x_{2,1})^2+x_{4,2}^2+x_{4,3}^2=l_5\\ (x_{4,1}-x_{3,1})^2+(x_{4,2}-x_{3,2})^2+x_{4,3}^2=l_6 \end{cases} $$

前两个方程相减，消掉 $x_{4,2}^2+x_{4,3}^2$，求出 $x_{4,1}$ 然后 $(x_{4,1}-x_{2,1})^2$ 和 $(x_{4,1}-x_{3,1})^2$ 都变成了已知的数，移到右边，后两个方程相减求出 $x_{4,2}$，最后带入求出 $x_{4,3}$。

后面的点也应该是类似的形式，对于每相邻两个方程把已知量移到右边然后相减，就可以求出一个维度的值，最后再统一带入求出最后一个维度的值。

然后我们发现，在这之后，第二部分似乎也解决了：后 $n-k-1$ 个点只需要问前 $k+1$ 个点就可以，那么就相当于在求第 $k+1$ 个点的基础上又多了一个方程，也就是说可以用原来的最后一个方程和多出来的这个方程用一样的方法求出最后一个维度的值，然后就不用带入了。

这种做法相对高斯消元而言，难度更低，代码长度和代码运行时间也会小一点。