Task

Given a dataset, fit ridge regression for each of several regularization strengths and return the L2 norm of the weight vector for each. The ridge solution is w = (X^T X + λI)^{-1} X^T y; for λ = 0 use the ordinary least-squares solution. Increasing λ shrinks the weight norm toward zero.

Input

• Line 1: n d k — number of samples, number of features, number of lambda values
• Lines 2 to n+1: x_1 ... x_d y — feature values followed by the target
• Line n+2: λ_1 λ_2 ... λ_k — lambda values separated by spaces

Output

Print the L2 norm of the weight vector for each lambda, space-separated on one line, with up to 10 significant digits each.

Example

Input:

6 2 4
1 2 5
2 1 4
3 4 9
4 3 8
5 6 13
6 5 12
0.0 0.5 1.0 5.0

Output:

1.807165428 1.765731198 1.736793199 1.639476739

Scaffolding

Submit a Python file defining:

def l2_regularization(X: list[list[float]], y: list[float],
                      lambdas: list[float]) -> list[float]:
    ...

Receives a feature matrix, target vector, and a list of regularization strengths; returns the L2 norm of the weight vector for each lambda value.