Задача C. One Rule ≡

Условие

Требуется реализовать классификатор, использующий алгоритм One Rule.

Формат входных данных

Первая строка входных данных содержит два целых числа N и K — количество примеров в обучающей выборке и количество признаков соответственно.

Вторая строка содержит K слов, разделённых пробелом — названия признаков объектов.

Следующие N строк содержат обучающую выборку, каждая строка содержит по K + 1 слов, первые K слов описывают значения признаков, слово номер K + 1 содержит метку класса — 0 или 1.

Следующая строка содержит одно целое число M — количество примеров в тестовой выборке.

Далее идёт тестовая выборка, содержащая M строк по K слов. Гарантируется, что каждое значение каждого признака встречается в обучающей выборке хотя бы один раз.

Формат выходных данных

Выходные данные должны содержать M чисел — результаты классификации алгоритма One Rule после обучения на первых N примерах.

В случае если несколько признаков дают одинаковый результат на обучающей выборке, то следует выбрать тот, который встречается раньше.

Если по какому-то значению можно с одинаковой вероятностью предсказать как 0 так и 1, то следует предсказывать 1.

Ограничения

1 ≤ N, M, K ≤ 100

Суммарная длина строк не превосходит 10⁵

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

10 4
Outlook Temperature Humidity Windy
overcast hot high FALSE 1
sunny mild high FALSE 0
overcast mild high TRUE 1
rainy mild normal FALSE 1
overcast hot normal FALSE 1
rainy mild high FALSE 1
rainy cool normal FALSE 1
rainy mild high TRUE 0
sunny hot high FALSE 0
sunny hot high TRUE 0
4
rainy cool normal TRUE
sunny cool normal FALSE
overcast cool normal TRUE
sunny mild normal TRUE

1
0
1
0