Task

Fit a Lasso regression model using coordinate descent with 100 iterations. For each feature j in a round-robin pass, compute the partial residual r = y - Xw + w_jXj, then set wj using the soft-thresholding rule: wj = sign(ρ) * max(0, |ρ| - λ) / ||Xj||², where ρ = Xj^T r and ||Xj||² = Xj^T Xj. Initialize w to zero. The L1 penalty drives small coefficients exactly to 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 0.5
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.750001907 1.74999822

Scaffolding

Submit a Python file defining:

def lasso_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.