APPROXIMATE PROBLEM WARNING
Metro
There are N metro stations in a city. The distance between each two station is a fixed integer x. Your task is to construct some metro lines across the stations.
We define a cost from station A to station B as the minimum of these two rules:
 if we can reach B by hopping on some line of metro and hop off it after K stations, the cost is K*x

if we can reach B by reaching station C with the cost of I, and we can reach B from C with the cost of J, then the cost is I+J+y where y is given.
Now there are
The boss of the company gives you three requirements:
 "avg" the average cost of every visitor is as small as possible

"max" the maximum cost of every visitor is as small as possible

"mix" the average cost of the average cost of every visitor and the maximum cost of every visitor is as small as possible
Input
You are given the integer N(N<=1000) and the matrix A of size N*N.
You are given x and y too. (x,y<=1000)
Then you are given the requirement: "avg" "max" or "mix"
Output
Print the metro lines. You can use at most N lines.
Scoring
Your answer will be scored according to the requirement.
Example
Input
N=5
x=1,y=3
A={ {0,0,0,0,1},{1,0,0,1,0},{1,1,1,1,1},{0,1,0,0,0},{1,0,0,0,0} }
(requirement is ignored)
Output
2 lines
line 1: 1 <> 3 <> 5
line 2: 2 <> 3 <> 4
Explain
the maximum cost is the visitor from 2 to 1, which is 1+1+3=5
the cost from 1 to 5 and 2 to 4 and vice versa is 2
the cost from 3 to 1/2/4/5 is 1
the cost from 3 to 3 is 0