Task

Solve ordinary least-squares regression using the normal equations: w* = (X^T X)^{-1} X^T y. Then compute the training MSE = mean((Xw - y)²). The normal equations give the unique closed-form minimiser of the sum of squared residuals when X^T X is invertible.

Input

• Line 1: n d — number of samples, number of features
• Lines 2 to n+1: x_1 ... x_d y — feature values followed by the target

Output

• Line 1: the weight vector space-separated, with up to 10 significant digits each
• Line 2: the training MSE as a single float with up to 10 significant digits

Example

Input:

4 2
1.0 2.0 5.0
2.0 1.0 4.0
3.0 4.0 10.0
4.0 3.0 9.0

Output:

0.8793103448 1.879310345
0.0775862069

Scaffolding

Submit a Python file defining:

def normal_equations(X: list[list[float]], y: list[float]) -> tuple[list[float], float]:
    ...

Receives a feature matrix and target vector; returns a tuple (weights, mse) where weights is the OLS solution and mse is the mean squared training error.