题目描述

小 C 所在的地方有 $n$ 个城市，$n^2$ 个公路，第 $i$ 个城市到第 $j$ 个城市有一个单向公路，小 C 通过这个公路需要花费 $a_{i,j}$ 单位时间。每个城市都有繁华程度 $c_i$

小 C 若从一个城市到另一个城市，小 C 会在路径上繁华程度最大的城市 $k$，停留 $c_k$ 单位时间，同时，小 C 想要使经过的时间尽可能短

你需要输出小 C 任意两个城市间所花费的时间，保证一定存在一条路径。

输入格式

第一行一个整数 $n$，表示城市数量。

第二行 $n$ 个整数 $c_i$，表示城市的繁华程度。

接下来 $n$ 行，每行 $n$ 个数 $a_{i,j}$，第 $i$ 行第 $j$ 列表示有一条从 $i$ 到 $j$ 的单向道路，小 C 通过这个公路需要花费 $a_{i,j}$ 单位时间。

输出格式

输出共 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 列表示小 C 从第 $i$ 个城市到第 $j$ 个城市所花时间。

4
2 4 3 6
2 1 8 4
7 3 6 3
5 8 2 9
3 9 2 1

2 5 11 10
11 4 10 9
8 10 3 15
9 10 8 6

提示

$n\le 500, c_i\le 10^{18}, w\le 10^{16}$