Task

Evaluate the effect of tree depth on training MSE by building a full regression decision tree at each specified depth and computing in-sample mean squared error. At each node, choose the feature and threshold that maximise variance reduction (gain = var(parent)n - var(left)|left| - var(right)*|right|); leaf nodes predict the mean of their samples. Report MSE = mean((pred - y)²) over all training points for each depth. This mirrors hyperparameter search in gradient-boosted tree libraries.

Input

• Line 1: n k — number of training samples, number of depth values to test
• Lines 2 to n+1: x y — 1D training feature and target value
• Line n+2: d_1 d_2 ... d_k — tree depths to evaluate

Output

Print the training MSE for each depth, space-separated on one line, with up to 10 significant digits each.

Example

Input:

8 3
1.0 2.0
2.0 4.0
3.0 6.0
4.0 8.0
5.0 10.0
6.0 12.0
7.0 14.0
8.0 16.0
1 2 3

Output:

5 1 0

Scaffolding

Submit a Python file defining:

def xgboost_tuning(x_train: list[float], y_train: list[float],
                   depths: list[int]) -> list[float]:
    ...

Receives 1D training data, targets, and a list of tree depths; returns the training MSE for each depth as a list of floats.