Island

Memory limit: 32 MB

On an island of the shape of a convex polygon with sides, there are situated countries. Each country has a territory in the shape of triangle, which vertices are placed at the vertices of the polygon. There are no countries which border exactly with two different countries (therefore, each country borders with only one or three countries). It implies, that there are exactly countries bordering with one country only (these are seaside countries) and countries bordering with three neighbours (these are inland countries). Seaside countries are numbered from to , inland countries have numbers from to . When we travel from one country to another, we are obliged to pay a charge on the border. Charges may be different on different borders, but crossing a border costs the same amount of money in both directions.

For each two countries , from seaside countries, it is known how much one has to pay traveling from to , assuming that the land route from one country to the other through the least number of borders was chosen. The task is to find all the charges on the island. For each seaside country there should be given the number of neighbouring country and the charge on the border. Moreover, for each inland countries there should be given numbers of three neighbouring countries and the charges on borders.

Task

Write a program which:

• reads from the standard input the sums of border charges on routes between seaside countries,
• finds for each country its neighbours,
• computes border charges on the island,
• writes the results to the standard output.

Input

In the first line of the standard input there is one positive integer , . This is the number of seaside countries. In each of the following lines there are non-negative integers separated by single spaces. The number , on the -th position in the -th line, is equal to the sum of border charges on the route (through the least number of borders) from the -th country to the -th country. We assume that the charge on each border is an integer from the interval . Of course, and .

Output

In each of the first lines of the standard output there should be written two integers separated by a single space. The first number in the -th line should be the number of the country, which borders with the country number . The second number is the charge on the border between these two countries. In each of the following lines there should be written six integers separated by single spaces. In the line number , , the first - number of the first country bordering with the -th country, the second - the charge on their border, the third - number of the second country bordering with the -th country, the forth - the charge on the second border, the fifth - the number of the third country bordering with the -th country, the sixth - the charge on the third border. Inland countries are numbered from to .

Example

For the input data:

7
0 8 10 8 13 11 14
8 0 8 10 11 5 12
10 8 0 12 5 11 6
8 10 12 0 15 13 16
13 11 5 15 0 14 3
11 5 11 13 14 0 15
14 12 6 16 3 15 0

the correct result is:

12 3
10 1
9 1
12 5
8 1
10 4
8 2
5 1 7 2 9 3
3 1 8 3 11 4
2 1 6 4 11 2
9 4 10 2 12 2
1 3 4 5 11 2

Sample input corresponds to this picture:

Task author: Wojciech Guzicki.