Task

For 1D ridge regression, the closed-form solution is:

w*(λ) = (Xᵀy) / (XᵀX + λ)

where λ ≥ 0 is the regularization strength.

Given Xᵀy and XᵀX, compute w(λ) and the shrinkage ratio w(λ) / w*(0) for each λ in a given list.

Note: w*(0) = Xᵀy / XᵀX is the OLS solution (no regularization).

Input

• Line 1: float xty — Xᵀy (dot product of feature vector and label vector)
• Line 2: float xtx — XᵀX (sum of squared feature values); guaranteed > 0
• Line 3: integer k — number of λ values
• Lines 4 to 3+k: one float per line, the λ values (all ≥ 0)

Output

For each λ in order, print two values: w_lambda shrinkage

• w_lambda = w*(λ)
• shrinkage = w(λ) / w(0)

Print with 10 significant figures ({:.10g}).

Example

Input

10.0
5.0
3
0.0
5.0
45.0

Output

2 1
1 0.5
0.2 0.1

Notes

• Track M: pure Python math, no NumPy required.
• The regularization path visualises how the ridge coefficient shrinks monotonically toward 0 as λ → ∞.
• At λ = 0 the shrinkage ratio is exactly 1 (OLS); at λ → ∞ it approaches 0.

Scaffolding

def reg_path(xty: float, xtx: float, lambdas: list[float]) -> list[tuple[float, float]]:
    """
    Returns list of (w_lambda, shrinkage) for each lambda.
    w_lambda  = xty / (xtx + lam)
    shrinkage = w_lambda / w_ols   where w_ols = xty / xtx
    """
    pass