Problem Statement

Implement a Gaussian Naive Bayes classifier: train on labeled data and predict class labels for test points.

Training (fit): For each class c:

• Prior: π_c = n_c / n (fraction of training points in class c)
• Feature means: μ_cd = mean of feature d in class c
• Feature variances: σ²_cd = var of feature d in class c (biased, ddof=0) + 1e-9 for numerical stability

Prediction (predict): For each test point x, compute the log posterior for each class:

log P(c|x) ∝ log π_c + Σ_d log N(x_d; μ_cd, σ²_cd)

where log N(x; μ, σ²) = -0.5 * [log(2π σ²) + (x-μ)²/σ²]. Predict the class with the highest log posterior.

Function signature:

def gaussian_nb(X_train: list, y_train: list, X_test: list) -> list:
    # returns list of predicted integer class labels

Input Format

Line 1: n d — number of training points and number of features
Lines 2..n+1: d feature values followed by class label (all space-separated)
Line n+2: m — number of test points
Lines n+3..n+m+2: d space-separated feature values per test point

Output Format

m lines: one predicted class label per line

Example

Input:

6 2
0.0 0.0 0
1.0 0.0 0
0.0 1.0 0
10.0 10.0 1
10.0 11.0 1
11.0 10.0 1
2
0.5 0.5
9.5 9.5

Output:

0
1

Notes

• The 1e-9 epsilon added to variances prevents division by zero when a feature is constant within a class.
• Log-space computation is preferred over direct probability multiplication for numerical stability.