Задача 03A. Наивный байесовский классификатор ≡

Условие

Пусть задан некоторый язык, описываемый множеством слов W, |W| = m, m ∈ N. Требуется построить наивный байесовский классификатор f: B↦ C = {i}k − 1i = 0, где {0, 1}^m ⊇ B = ⋃l ∈ N,μ ∈ W^l{δ_w(μ)|w ∈ W} — множество представлений всех возможных сообщений составленных на языке W в виде мешка слов, δ_w — мера Дирака, δ_x(A) = {1,x ∈ A,0,x ∉ A..

При этом процесс классификации происходит следующим образом

1. Сформировать базовый классификатор с априорными вероятностями классов p(c ∈ C) = 1k и условными вероятностями слов p(w ∈ W|c ∈ C) = 1m;
2. Для каждого поступившего сообщения μ_i и его класса c_i
1. Получить предсказание ^c_i по μ_i с использованием текущего классификатора;
2. Обновить классификатор с использованием сообщения μ_i и настоящего значения его класса c_i.

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

Первая строка входного файла содержит натуральные числа n, m, k — количество сообщений, мощность языка и количество классов соответственно. В каждой их следующих n строк содержится m чисел 0 или 1 и одно натуральное число c_i — представление сообщения в виде мешка слов и значение его класса.

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

Выходной файл должен содержать n натуральных чисел — предсказанное значение класса каждого сообщения на момент его получения.

Ограничения

10 ⩽ n ⩽ 7500

8 ⩽ m ⩽ 100

2 ⩽ k ⩽ 10

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

10 8 2
0 1 1 1 1 0 0 1 1
1 0 1 0 0 1 0 0 0
1 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 0
0 1 0 1 1 1 1 0 1
1 0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 1 1
1 0 0 0 0 1 0 1 0
1 1 1 1 0 1 1 1 0
0 1 0 1 1 0 0 0 1

0
0
1
0
1
0
1
0
1
1