Reconstructing Flavor Embeddings

Vector embeddings are a common tool in machine learning systems. In this problem, you are given several training results extracted from a flavor embedding model. Each training result consists of the coordinates of a known flavor embedding (a vector in \(\mathbb{R}^D\)) and the Euclidean distance from this known flavor to a missing flavor embedding \(X\). The goal is to recover \(X\) so that it is consistent with all the given distances.

For each training pair \( (P_i, d_i) \), where \(P_i\) is a known \(D\)-dimensional vector and \(d_i\) is the distance from \(X\) to \(P_i\), we have:

[ |X - P_i| = d_i \quad \text{for } i = 1, 2, \dots, N. ]

Squaring both sides gives:

[ |X - P_i|^2 = d_i^2. ]

If we choose the first training data \((P_1, d_1)\) as a reference and subtract its equation from the others, we obtain for \(i \ge 2\):

[ |X - P_i|^2 - |X - P_1|^2 = d_i^2 - d_1^2. ]

Simplifying using the properties of the Euclidean norm, this becomes a system of linear equations:

[ 2(P_i - P_1)^T X = |P_i|^2 - |P_1|^2 + d_i^2 - d_1^2, \quad i = 2, 3, \dots, N. ]

It is guaranteed that the training data is consistent and determines a unique solution. Your task is to solve this system and output the missing vector \(X\).

inputFormat

The first line contains two integers D and N, where D is the dimension of the embedding vectors and N is the number of training results. Each of the next N lines contains D+1 real numbers: the first D numbers are the coordinates of a known flavor embedding, and the last number is the Euclidean distance from the missing embedding to that known flavor.

outputFormat

Output D real numbers on a single line, representing the coordinates of the reconstructed embedding vector. Answers will be accepted if each coordinate has an absolute or relative error of at most (10^{-6}).

sample

2 3
0 0 5
5 0 4.472135955
0 5 3.16227766

3 4