说明

图上有 N 个城市，任意两城市间有直通的路或没有路。每条路有过路费，并且经过每个城市都要交税。

注意：起点与终点不需要交税。

输入格式

第 1 行输入一个整数 N ，表示城市的数量

后面 N 行中，第 i 行输入 N 个数 a[i][j]，表示第 i 个城市到第 j 个城市的直通路过路费，-1 表示没有直通路。

接下来一行输入 N 个数，第 i 个数表示第 i 个城市的税。

再后面有若干行，每行输入两个数，表示起点和终点城市，若两个数 -1，结束。

输出格式

对给定的每两个城市，输出最便宜的路径经过哪些点，以及最少费用。如果两个路径费用相同，输出编号小的路径。

样例

5
0 51 -1 -1 101
-1 0 -1 -1 45
69 -1 0 -1 30
-1 -1 10 0 16
85 -1 32 20 0
15 10 11 7 8
1 4
2 3
-1

1-->5-->4 129
2-->5-->3 85

提示

数据范围：

2 <= N <= 500