Problem Statement

Implement the E-step of the Expectation-Maximization algorithm for a 1D Gaussian Mixture Model (GMM).

Given n data points and k Gaussian components with their means, variances, and mixture weights, compute the responsibility matrix — the posterior probability that each data point was generated by each component.

Formula for each point x_i and component j:

r_ij = π_j * N(x_i; μ_j, σ²_j) / Σ_{l=1}^{k} π_l * N(x_i; μ_l, σ²_l)

where N(x; μ, σ²) = (1/√(2π σ²)) * exp(-0.5*(x-μ)²/σ²).

Function signature:

def gmm_e_step(X: list, means: list, vars: list, weights: list) -> list:
    # returns n x k matrix of responsibilities (list of lists)

Input Format

Line 1: n k — number of data points and components
Line 2: n space-separated floats — data values
Line 3: k space-separated floats — means
Line 4: k space-separated floats — variances
Line 5: k space-separated floats — mixture weights (sum to 1)

Output Format

n lines, each with k space-separated responsibility values (10 significant figures)

Example

Input:

3 2
0.0 5.0 10.0
0.0 10.0
1.0 1.0
0.5 0.5

Output:

1 1.928749848e-22
0.5 0.5
1.928749848e-22 1

Notes

• Point 0.0 is very close to mean 0.0, so it has responsibility ≈ 1 for component 0.
• Point 5.0 is equidistant from both means (with equal weights and variances), giving 0.5/0.5.
• Each row sums to 1.0 (it is a proper posterior distribution over components).