Task

Implement gradient boosting for regression using depth-1 decision stumps. Starting from zero predictions, fit n_trees stumps sequentially on the current residuals y - pred. Each stump selects the threshold that minimises total squared error and predicts the mean residual in each leaf. After fitting, update training predictions as pred += lr * stump_prediction. Once all stumps are trained, produce test-set predictions by summing all stump contributions scaled by lr.

Input

• Line 1: n n_trees lr — number of training samples, number of boosting rounds, learning rate
• Lines 2 to n+1: x y — training feature and target value
• Line n+2: m — number of test points
• Lines n+3 to n+m+2: x — test feature values (one per line)

Output

Print the predicted values for the test points space-separated on one line, with up to 10 significant digits each.

Example

Input:

5 3 0.1
1.0 2.0
2.0 4.0
3.0 5.0
4.0 8.0
5.0 10.0
3
1.5
3.5
5.0

Output:

0.9936666667 2.439 2.439

Scaffolding

Submit a Python file defining:

def gradient_boosting(x_train: list[float], y_train: list[float],
                      x_test: list[float], n_trees: int, lr: float) -> list[float]:
    ...

Receives 1D training data, targets, test inputs, the number of boosting rounds, and a learning rate; returns a list of predicted values for the test points.