Конвейерная линия
Последний работник на производственной линии на фабрике Automated Composed Machinery обеспокоен. Она знает, что её работа под угрозой, если её производительность не увеличится. Её задача заключается в сборке набора деталей в определённой последовательности, но время, затрачиваемое на сборку деталей a и b, а затем c, может отличаться от времени, затрачиваемого на сборку деталей b и c, а затем a с полученным компонентом. В каждый момент можно собирать только две последовательные детали, и после их сборки они рассматриваются как новая деталь с точки зрения времени, необходимого для дальнейшей сборки.
Чтобы помочь ей, вам нужно найти оптимальный способ собрать все компоненты. Входные данные для вашей программы будут представлять собой набор символов, обозначающих (типы) деталей, и так называемую таблицу сборки, представляющую время, необходимое для их сборки, а также тип полученного компонента. Например, у нас могут быть два символа {a, b}, и следующая таблица:
Это означает, например, что две детали типа a и a могут быть собраны за 3 минуты, и результатом будет компонент типа b, при этом время, необходимое для его сборки с другой деталью, скажем, типа a, составляет 6 минут, и так далее. Обратите внимание, что таблица не симметрична, т.е. сборка b и a может быть более трудоемкой, чем a и b.
Для последовательности компонентов, обозначенной aba, возможны два решения:
(ab)a = ba = a с временем time(ab) + time(ba) = 5 + 6 = 11.
a(ba) = aa = b с временем time(ba) + time(aa) = 6 + 3 = 9.
Таким образом, результат для этого случая будет деталь типа b за 9 минут (обозначается 9-b).
Входные данные
Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай начинается с строки, содержащей натуральное число k (1 ≤ k ≤ 26), за которым следует строка с k символами (буквами в диапазоне [a-z]), разделенными пробелами. Следующие k строк содержат таблицу сборки: i-я строка содержит k пар вида time-result, где time — это целое число от 0 до 1 000 000 включительно, а result — символ, принадлежащий предыдущему набору. j-я пара в i-й строке представляет время для сборки деталей типов, представленных i-м и j-м символами, вместе с типом полученного компонента. После таблицы идет строка с целым числом n, указывающим количество строк, которые следуют, каждая строка представляет собой строку длиной не более 200 символов. Каждая из этих строк — это последовательность компонентов, которые нужно собрать вместе в правильном порядке.
Входные данные заканчиваются строкой, содержащей '0', которая не должна обрабатываться.
Выходные данные
Для каждого тестового случая выведите n строк, каждая из которых содержит целое число времени и символ результата в формате time-result. Каждая строка представляет минимальное время и тип полученного компонента для соответствующего случая во входных данных. В случае ничьей между несколькими возможными результатами с одинаковым минимальным временем выберите из них деталь, буква типа которой появляется первой в строке, содержащей k символов в начале тестового случая. (Например, если эта строка была a c b и можно получить как c, так и b с минимальной стоимостью 5, выведите 5-c).
Между выводом разных тестовых случаев должна быть пустая строка.