Задача D. Вторая задача для СММ ≡

Условие

Скрытая модель Маркова предназначена для описания стохастически эволюционирующих во времени процессов. Она представляет из себя ориентированный граф состояний, ребрам которого приписаны веса a_ij, равные вероятностям перехода из состояния i в j, причем диагональным элементам соответствует вероятность того, что система останется в том же состоянии.

Кроме того, для каждого состояния известна вероятность b_i того, что оно окажется начальным.

Для стороннего наблюдателя состояние не является доступной напрямую информацией — оно скрыто. Зато он может видеть некоторый производимый системой сигнал, распределение вероятностей которого зависит от состояния. Таким образом, задание модели завершается указанием матрицы c_ij — вероятности наблюдать сигнал j при том, что система находится в состоянии i.

Вторая задача для СММ состоит в том, чтобы по данной модели a_ij b_i c_ij установить последовательность состояний w₁, ..., w_k, которая бы являлось наиболее вероятной для данной последовательности сигналов s₁, ... , s_k. Напишите программу, которая решает эту задачу.

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

Первая строка входного файла содержит числа N, M, K — количество состояний, уровней сигнала и длину последовательности наблюдений соответственно.

Вторая строка содержит N чисел b_i.

Следующие N строк содержат по N действительных чисел от 0 до 1 и задают матрицу a_ij, где i — номер строки, а j — столбца. Сумма элементов каждой строки равна единице.

Следующие N строк содержат по M чисел от 0 до 1 и задают матрицу c_ij.

Последняя строка содержит K целых чисел от 1 до M и задает последовательность наблюдений s_i

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

В выходной файл выведите K целых чисел w_i.

Ограничения

1 ≤ N, M, K ≤ 100

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

3 3 8
0 0 1
0.4 0.3 0.3
0.2 0.6 0.2
0.1 0.1 0.8
1 0 0
0 1 0
0 0 1
3 3 3 1 1 3 2 3

3 3 3 1 1 3 2 3