Driving in Optimistan

Optimistan is a country on a single island. A huge desert covers the middle of the island, so almost everyone lives in port towns along the coast. As the name suggests, the people of Optimistan like to optimise everything, so they built only the roads needed to connect all port towns and not a single extra road. There is therefore exactly one way to get from one port town to another without visiting the same place twice.

The government put distance signs along one side of every road at intervals of 1 kilometre. When you drive from one port town to another, you pass the first sign in the port town you start from and then one more sign every kilometre. Each sign carries the shortest distance to every port town, each distance written on a separate small plate that points towards that town.

The signs also guide drivers at intersections. Every intersection, meaning every point where three or more roads meet, has a sign standing at it, so the distance from an intersection to each port town is a whole number of kilometres.

Together with the rule that no extra road was built, the table of distances between the port towns determines the whole road network.

You bought a tourist guide of Optimistan. It has no map, but it does contain a table with the shortest distance between every pair of port towns. After computing the average shortest distance over all pairs of port towns, you started thinking about what the average of the numbers on a sign would be if the signs also carried the shortest distance to every other sign. Compute the average shortest distance over all pairs of two different signs. Pairs are unordered.

The input consists of:

• one line with an integer $n$ ($2 \le n \le 500$), the number of port towns;
• $n-1$ lines, the $i$th of which contains $n-i$ integers. The $j$th integer on the $i$th line is the distance in kilometres between port town $i$ and port town $i+j$, at least 1 and at most $10^6$.

The distances come from a road network in which exactly one path between two port towns does not visit the same place twice. Every road can be driven in both directions.

Print the average distance in kilometres over all pairs of two different signs on one line, as an irreducible fraction p/q where $p$ and $q$ are coprime positive integers. Print the denominator even when the average is a whole number, for example 5/1.

If the road network determined by the table has an intersection whose distance to the port towns is not a whole number of kilometres, the positions of the signs cannot be determined. Print impossible in that case.