AT_past17_l 割引券

There are $ N $ cities numbered $ 1 $ through $ N $ . Every pair of different cities is connected by a bidirectional toll road. There is a voucher that can be used on any road to get a discount on the toll. The toll of the road between city $ i $ and city $ j $ $ (i \lt j) $ is $ a_{i,j} $ yen; with the voucher, it is $ b_{i,j} $ yen. $ (b_{i,j} \lt a_{i,j}) $ Find the following value for all pairs of cities $ (i, j) $ such that $ i \lt j $ : - the minimum amount of money required to travel from city $ i $ to city $ j $ , using the voucher at most once in total.

The input is given from Standard Input in the following format: > $ N $ $ a_{1,2} $ $ a_{1,3} $ $ \dots $ $ a_{1,N} $ $ a_{2,3} $ $ \dots $ $ a_{2,N} $ $ \vdots $ $ a_{N-1,N} $ $ b_{1,2} $ $ b_{1,3} $ $ \dots $ $ b_{1,N} $ $ b_{2,3} $ $ \dots $ $ b_{2,N} $ $ \vdots $ $ b_{N-1,N} $

Print the answer in the following format. Here, $ c_{i,j} $ denotes the minimum amount of money required to travel from city $ i $ to city $ j $ , using the voucher at most once. > $ c_{1,2} $ $ c_{1,3} $ $ \dots $ $ c_{1,N} $ $ c_{2,3} $ $ \dots $ $ c_{2,N} $ $ \vdots $ $ c_{N-1,N} $

### Sample Explanation 1 For example, you can travel from city $ 1 $ to city $ 3 $ using the voucher at most once for a total cost of $ 4 $ yen, which is the minimum, as follows: - Travel from city $ 1 $ to city $ 4 $ for a cost of $ 1 $ yen, using the voucher. - Travel from city $ 4 $ to city $ 3 $ for a cost of $ 3 $ yen, without using the voucher. ### Constraints - $ 2 \leq N \leq 300 $ - $ 1 \leq b_{i,j} \lt a_{i,j} \leq 10^4 $ $ (i \lt j) $ - All input values are integers.