Task

Train a logistic regression model by gradient descent. At each step compute predictions p = σ(Xw) where σ(z) = 1/(1+e^{-z}), then update weights as w -= lr * X^T(p - y) / n. Repeat for n_iter steps, starting from w = 0. The cross-entropy gradient X^T(p - y)/n points in the direction that reduces log-loss.

Input

• Line 1: n d lr n_iter — number of samples, number of features, learning rate, number of iterations
• Lines 2 to n+1: x_1 ... x_d label — feature values followed by the binary label (0 or 1)

Output

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

Example

Input:

6 2 0.1 100
1.0 2.0 1
2.0 1.0 1
3.0 4.0 1
-1.0 -2.0 0
-2.0 -1.0 0
-3.0 -4.0 0

Output:

1.116833175 1.168202853

Scaffolding

Submit a Python file defining:

def logistic_gd(X: list[list[float]], y: list[int],
                lr: float, n_iter: int) -> list[float]:
    ...

Receives a feature matrix, binary labels, learning rate, and iteration count; returns the learned weight vector as a list of floats.