Task

Fit a ridge regression model using the closed-form solution w = (X^T X + λI)^{-1} X^T y, where λ is the regularization strength and I is the identity matrix of size d×d. The L2 penalty term λI makes the system full-rank and shrinks the weights toward zero.

Input

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

Output

Print the learned weight vector space-separated on one line, with up to 10 significant digits each.

Example

Input:

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

Output:

0.9039548023 1.570621469

Scaffolding

Submit a Python file defining:

def ridge_regression(X: list[list[float]], y: list[float], lam: float) -> list[float]:
    ...

Receives a feature matrix, target vector, and regularization strength; returns the learned weight vector as a list of floats.