B. Алгогонки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

PMP готовится стать воином. Он много тренируется, но результаты пока не очень. На этот раз вместо контестов по программированию он решил состязаться в гонках, чтобы поднять дух победы. Он решил выбрать соревнование, которое помимо прочего использует его алгоритмические навыки.

AlgoRace — особая лига гонщиков, где разные команды соревнуются в стране с n городами. Города пронумерованы от 1 до n. Каждые два различных города страны связаны друг с другом двусторонней дорогой. Каждая команда должна представить на соревновании одного водителя и набор автомобилей.

Соревнование проводится в r раундов. На i-м раунде водители стартуют в городе si, а финишируют в городе ti. В течении этого раунда водителям разрешено менять автомобили не более ki раз. Поменять автомобиль можно в любом городе, это действие не занимает времени. Один автомобиль можно использовать несколько раз за раунд, но общее число пересадок не должно превышать ki. Водители могут свободно выбирать свой путь к месту назначения.

PMP-воин подготовил m типов специально сконструированных автомобилей. Кроме того, PMP водит по-разному в зависимости от свойств автомобиля и дороги, следовательно, автомобиль проезжает разные дороги (или одну дорогу в разных направлениях) за разное время.

PMP-воин хочет разработать лучшие стратегии выбора автомобилей и дорог в каждом раунде, чтобы максимизировать шансы выиграть кубок. Для каждого раунда надо найти минимальное время, необходимое для его прохождения.

Входные данные

Первая строка содержит три целых числа, разделенных пробелом n, m, r (2 ≤ n ≤ 60, 1 ≤ m ≤ 60, 1 ≤ r ≤ 105) — количество городов, количество различных типов машин и количество раундов в соревновании, соответственно.

Затем последуют m матриц размера n × n, состоящих из целых чисел от 0 до 106 (включительно), описывающие время, необходимое для одной машины для того, чтобы проехать разные дороги. Целое число, которое следует k-ым в j-ой строке i-й матрицы, обозначает время, за которое i-ый автомобиль проедет дорогу из j-го города в k-ый город. Заданные матрицы необязательно симметричны, но их диагональ всегда нулевая.

В следующих r строках содержатся описания раундов, i-ая из них содержит разделенные пробелом целые числа si, ti, ki (1 ≤ si, ti ≤ n, si ≠ ti, 0 ≤ ki ≤ 1000) — номер города-старта, номер города-финиша и количество допустимых пересадок в i-ом раунде, соответственно.

Выходные данные

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

Примеры
Входные данные
4 2 3
0 1 5 6
2 0 3 6
1 3 0 1
6 6 7 0
0 3 5 6
2 0 1 6
1 3 0 2
6 6 7 0
1 4 2
1 4 1
1 4 3
Выходные данные
3
4
3
Входные данные
4 2 3
0 7 3 3
8 0 10 5
1 1 0 4
8 9 2 0
0 3 3 9
7 0 4 9
3 8 0 4
4 8 9 0
2 3 3
2 1 3
1 2 2
Выходные данные
4
5
3
Примечание

В первом примере во всех раундах PMP проезжает от города #1 до города #2, затем до города #3 и наконец до города #4. Но последовательность типов машин, которые он использует, в первом раунде (1, 2, 1), а во втором раунде (1, 2, 2). В третьем раунде он может поменять машину три раза. Здесь PMP использует такую же стратегию как и в первом раунде, меняя машину только два раза.