Задача 03B. Байесовский классификатор ≡

Условие

Пусть задано вещественное пространство Rⁿ. Требуется написать программу, классифицирующую точки с использованием байесовского классификатора B(x) = arg maxi = 0,m − 1(π_i f_{Nk(μi, Σi)}(x)m − 1∏j = 0,i ≠ jλ_i,j), где m — количество классов, π_i — априорная вероятность класса, f_{Nk(μi, Σi)} — функция плотности многомерного нормального распределения N_k(μ_i, Σ_i) со средним μ_i и матрицей ковариации Σ_i, λ_i,j — штраф за ошибочною классификацию класса i в качестве класса j.

Формат входного файла

Первая строка входного файла содержит натуральные числа n, m, k, l — размерность пространства, количество классов, количество элементов обучающей и тестовой выборок соответственно. Далее следуют значения матрицы λ — m строк по m натуральных чисел. Далее следуют k строк обучающей выборки в формате x_i,0, x_i,1, …, x_{i,n − 1}, c_i, где x_i,j вещественные числа — координаты точки i, c_i ∈ {0,1,…,m − 1} — класс точки. Последние l строк содержат по n вещественных чисел — координаты точек тестовой выборки.

Формат выходного файла

Выходной файл должен содержать l целых чисел — предсказанные классы точек тестовой выборки.

Ограничения

n ∈ {2, 3}

2 ⩽ m ⩽ 9

2 ⩽ k, l ⩽ 10³

1 ⩽ λ_i,j ⩽ 5

Примеры тестов

2 2 6 2
0 1
1 0
1 1 0
1 2 0
2 1 0
-1 -1 1
-1 -2 1
-2 -1 1
2 2
-2 -2

0 1