Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено N точек, в которых может находиться клад. Все точки пронумерованы числами от 1 до N. Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером 1. Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером 1 никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.
Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.
Входные данные
В первой строке находится одно целое число N (1 ≤ N ≤ 15) — количество точек, отмеченных на карте. В последующих N строках находятся расстояния между точками. В (i+1)-й строке находятся N целых чисел d
i1,d
i2, d
iN — длины дорог от i-й точки до всех остальных. Гарантируется, что d
ij=d
ji, d
ii=0 и 0 <d
ij <100. В (N+2)-й строке находится одно целое число Q (1 < Q ≤ 1000) — количество вариантов вычеркивания точек для данной карты. В последующих Q строках содержится описание вариантов вычеркивания. Описание начинается с числа C (0 ≤ C < N) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие C чисел задают номера этих точек.
Выходные данные
Выведите Q строк. В каждой строке выведите одно целое число — длину минимального маршрута при соответствующем варианте вычеркивания точек.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
0 45 10
45 0 30
10 30 0
2
0
1 3 |
40
45 |
| 2 |
5
0 14 20 17 14
14 0 15 19 18
20 15 0 15 16
17 19 15 0 14
14 18 16 14 0
2
3 5 4 3
0 |
14
58 |