Task

Implement out-of-fold (OOF) target encoding with k-fold cross-validation.

For each training sample, compute its encoding as the mean target value from all folds except the fold containing that sample. This prevents target leakage within folds.

Algorithm:

1. Split training samples into k consecutive folds (samples 0..n-1 split into k equal groups; if n is not divisible by k, distribute the remainder to the first folds — i.e. the first n % k folds each get one extra sample)
2. For each fold f: encode each sample in fold f using the mean target of all samples NOT in fold f
3. For test samples: use the global training mean

Input

• Line 1: two integers n k — number of training samples and number of folds
• Lines 2 to n+1: label (0 or 1) — training labels in order
• Line n+2: integer n_test
• Lines n+3 to end: label — test labels (unused for encoding; output their test encodings using global train mean)

Output

• First n lines: OOF-encoded training values
• Next n_test lines: test encodings (global training mean for all)

Print all floats with 10 significant figures ({:.10g}).

Example

Input

6 2
1
1
1
0
0
0
2
1
0

Output

0
0
0
1
1
1
0.5
0.5

Explanation: k=2, so fold0 = indices [0,1,2] (labels [1,1,1]), fold1 = indices [3,4,5] (labels [0,0,0]).

• Samples in fold0 are encoded with the mean of fold1 = 0/3 = 0.0
• Samples in fold1 are encoded with the mean of fold0 = 3/3 = 1.0
• Global mean = 3/6 = 0.5; all n_test=2 test encodings are 0.5

Notes

• Track A: pure Python only — no NumPy, no scipy, no sklearn.
• The fold split is consecutive (not shuffled): fold 0 takes the first ceil(n/k) samples, and so on.

Scaffolding

def oof_encode(train_labels: list[int], k: int, n_test: int) -> tuple[list[float], list[float]]:
    """
    Returns (train_encoded, test_encoded).
    train_encoded[i] = mean of all training labels NOT in the same fold as i.
    test_encoded     = [global_train_mean] * n_test
    """
    pass