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 A_{i,j} visitors want to reach station j from station i by metro.
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. A_{i,j}\leq1000
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