Once the dwarf Quark came across a treasure map. There are N points marked on the map where the treasure can be found. All points are numbered from 1 to N. For each pair of points, Quark knows the length of the road connecting them. Quark starts his search from point number 1. Before starting his long journey, the cunning dwarf crosses out points where, in his opinion, there can be no treasure. It is guaranteed that point number 1 is never crossed out. After that, Quark chooses some route that passes through all the remaining points on the map. The route does not pass through the same point more than once. A quark can only walk on roads that connect uncrossed points.
Quark wants to choose a route of minimum length. It is necessary to find such a route for Quark.
Input
The first line contains one integer N (1 ≤ N ≤ 15) — the number of points marked on the map. The next N lines contain the distances between the points. The (i+1)-th line contains N integers d
i1,d
i2, d
iN — lengths of roads from the i-th point to all the others. It is guaranteed that d
ij=d
ji, d
ii=0 and 0 <d
ij <100 . The (N+2)th line contains one integer Q (1 < Q ≤ 1000) — the number of options for deleting points for this map. The following Q lines contain a description of the options for deletion. The description starts with the number C (0 ≤ C < N) — the number of points where, according to Quark, the treasure cannot be. The next C numbers give the numbers of these points.
Imprint
Print Q lines. In each line print one integer — the length of the minimum route with the corresponding option of deleting points.
Examples
| # |
Input |
Output |
| 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 |