Aquarium Seller

A seller specializing in cat aquariums plans to visit n cities, ensuring each city is visited exactly once. Your task is to help him determine the shortest possible route.

Input

The first line of the input contains a natural number n (1 ≤ n ≤ 13), representing the number of cities. The following n lines each contain n numbers, which represent the distances between the cities.

In the i-th line, the j-th number, a_{i,j}, indicates the distance between city i and city j (0 ≤ a_{i,j} ≤ 10^6, a_{i,j} = a_{j,i}, a_{i,i} = 0).

Output

On the first line of the output, print the length of the shortest route. On the second line, print n numbers indicating the sequence in which the cities should be visited.

Examples