Task

Implement a random forest of depth-1 decision stumps for binary classification. For each tree, draw a bootstrap sample (with replacement) of size n from the training set using the provided random seed, fit a Gini-optimal stump on all features, and store the stump. At prediction time, collect each stump's vote for a test point and return the majority-vote class (rounded mean of individual predictions).

Input

• Line 1: n d n_trees seed — training set size, number of features, number of trees, random seed
• Lines 2 to n+1: x_1 ... x_d label — feature values followed by the binary label (0 or 1)
• Line n+2: m — number of test samples
• Lines n+3 to n+m+2: x_1 ... x_d — feature values for each test sample

Output

Print the predicted class (0 or 1) for each test sample space-separated on one line.

Example

Input:

6 2 5 42
1.0 2.0 0
2.0 1.0 0
3.0 4.0 1
4.0 3.0 1
1.0 4.0 1
3.0 1.0 0
3
2.0 2.0
3.5 3.5
1.5 1.5

Output:

1 1 1

Scaffolding

Submit a Python file defining:

def random_forest(X_train: list[list[float]], y_train: list[int],
                  X_test: list[list[float]], n_trees: int, seed: int) -> list[int]:
    ...

Receives training features and labels, test features, number of trees, and a random seed; returns a list of predicted class labels for the test samples.