Task

Compute the bias-variance decomposition of ridge regression predictions on the training set. The ridge hat matrix is Hλ = X(X^T X + λI)^{-1} X^T and the bias matrix is Bλ = I - Hλ. Using the OLS fit as the true mean μ = X(X^T X)^{-1}X^T y: biassquared = ||Bλ μ||² = (Bλ μ)^T (Bλ μ); variance = σ² * trace(Hλ Hλ^T); total = (biassquared + variance + σ²) / n.

Input

• Line 1: n d lam sigma2 — number of samples, number of features, ridge parameter λ, noise variance σ²
• Lines 2 to n+1: x_1 ... x_d y — feature values followed by the target

Output

Print three values each on its own line: bias_squared, variance, total — each with up to 10 significant digits.

Example

Input:

4 2 1.0 0.5
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.1745094608
0.7054167066
0.3449815418

Scaffolding

Submit a Python file defining:

def ridge_bias_variance(X: list[list[float]], y: list[float],
                        lam: float, sigma2: float) -> tuple[float, float, float]:
    ...

Receives a feature matrix, target vector, ridge parameter, and noise variance; returns a tuple (bias_squared, variance, total).