History of OI -> VIII OI 2000/2001

 News About Olympic History of OI XVII OI 2009/2010 XVI OI 2008/2009 XV OI 2007/2008 XIV OI 2006/2007 XIII OI 2005/2006 XII OI 2004/2005 XI OI 2003/2004 X OI 2002/2003 IX OI 2001/2002 VIII OI 2000/2001 Stage III - results Stage II - results Stage I - results Problems Regulations Organization Hints Schedule Stats VII OI 1999/2000 VI OI 1998/1999 V OI 1997/1998 IV OI 1996/1997 III OI 1995/1996 II OI 1994/1995 I OI 1993/1994 OI books National team Olympic camps Photo gallery Links SIO MAIN

Island

 II stage contest, the first day

On an island of the shape of a convex polygon with 2n sides, there are situated 2n-2 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 n countries bordering with one country only (these are seaside countries) and n-2 countries bordering with three neighbours (these are inland countries). Seaside countries are numbered from 1 to n, inland countries have numbers from n+1 to 2n-2. 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 i,j from n seaside countries, it is known how much one has to pay traveling from i to j, 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 n-2 inland countries there should be given numbers of three neighbouring countries and the charges on borders.

Write a program which:

• reads from the text file WYS.IN 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 in the text file WYS.OUT.

### Input

In the first line of the text file WYS.IN there is one positive integer n, 4<=n<=100. This is the number of seaside countries. In each of the following n lines there are n non-negative integers separated by single spaces. The number di,j, on the j-th position in the i-th line, is equal to the sum of border charges on the route (through the least number of borders) from the i-th country to the j-th country. We assume that the charge on each border is an integer from the interval [1..100]. Of course, di,j=dj,i and di,i=0.

### Output

In each of the first n lines of the text file WYS.OUT there should be written two integers separated by a single space. The first number in the i-th line should be the number of the country, which borders with the country number i. The second number is the charge on the border between these two countries. In each of the following n-2 lines there should be written six integers separated by single spaces. In the line number i, n+1<=i<=2n-1,  the first - number of the first country bordering with the i-th country, the second - the charge on their border, the third - number of the second country bordering with the i-th country, the forth - the charge on the second border, the fifth - the number of the third country bordering with the i-th country, the sixth - the charge on the third border. Inland countries are numbered from n+1 to 2n-2.

### Example

For the input file WYS.IN:

```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 answer is the output file WYS.OUT (see the picture below):

 ```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 ```

Print friendly version