Task

Implement a leave-one-out (LOO) target encoder for a categorical feature.

Training encoding: For each training sample i in category c, encode it as the mean of the target values of all other training samples in the same category (excluding sample i itself).

Test encoding: For each test sample in category c, encode it as the mean of all training target values in category c. If category c was not seen during training, use the global training mean.

Input

• Line 1: integer n_train
• Lines 2 to n_train+1: category label (category is a string, label is 0 or 1)
• Line n_train+2: integer n_test
• Lines n_train+3 to end: category (one per line, test samples)

Output

• First n_train lines: LOO-encoded training values, one per line
• Next n_test lines: encoded test values, one per line

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

Example

Input

6
A 1
A 0
A 1
B 1
B 0
B 0
2
A
C

Output

0.5
1
0.5
0
0.5
0.5
0.6666666667
0.5

Notes

• Track A: pure Python / NumPy only — no pandas, no sklearn.
• When a category has only one training sample, the LOO encoding for that sample falls back to the global training mean (the category mean is undefined with the single sample removed).
• The global mean is computed over all training labels regardless of category.

Scaffolding

Submit a Python file defining:

def loo_target_encode(train: list[tuple[str, int]], test: list[str]) -> tuple[list[float], list[float]]:
    ...

Returns (train_encoded, test_encoded).