Task

Apply one proximal gradient (soft-thresholding) update step for the Lasso objective. Given current weights w, gradient of the smooth part g, step size alpha, regularization strength lam, and sample count n, compute the updated weights using the proximal operator of the L1 penalty. For each coordinate j: first take a gradient step uj = wj - alpha * gj, then apply soft-thresholding S(uj, lam/n) where S(u, t) = sign(u) * max(|u| - t, 0).

Input

• Line 1: d alpha lam n — number of dimensions, step size, regularization strength, sample count
• Line 2: w_1 ... w_d — current weight vector
• Line 3: g_1 ... g_d — gradient of the smooth part

Output

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

Example

Input:

3 0.1 0.5 10
2.0 0.05 -1.5
1.0 0.0 2.0

Output:

1.85 0 -1.65

Scaffolding

Submit a Python file defining:

def soft_threshold_update(w: list[float], g: list[float],
                          alpha: float, lam: float, n: int) -> list[float]:
    ...

Receives the current weights, the smooth-part gradient, the step size, regularization strength, and sample count; returns the updated weight vector after one soft-thresholding proximal step.