题目背景

小 X 在 Z 市长途奔波之后，他要去参加别人的晚宴。

题目描述

Z 市形如一个 $n \times n$ 的矩阵，小 X 打算仅使用瞬移机和时空穿越机到达别人的晚宴，若小 X 所在的位置 $(p,q)$ 满足 $l1_x \le p \le r1_x$ 且 $l2_y \le q \le r2_y(0 \le l1_x \le r1_x < x,0\le l2_y\le r2_y < y)$，那么小 X 就可以到达位置 $(x,y)$。

但是由于瞬移技术不太成熟以及时空穿越机的影响，瞬移时需花费 $w_p+w_q+w_x+w_y-p-q-x-y$ 秒（由于时空穿越机的特性，时间可能为负）。若下标不是正整数，瞬移机就会被损坏，所以小 X 只能到达都是正整数的下标。

现在小 X 在 $(1,1)$ 的位置，他要参加别人的晚宴，可是他目前不知道别人的晚宴在哪里，所以他想让你求，他到达每个地方 $(x,y)\text{ }\text{ }(1 \leq x,y \leq n)$ 所花费的最少时间，如果不能到达则输出 inf。

输入格式

第 $1$ 行一个整数 $n$，表示矩阵的大小。

第 $2$ 行 $n$ 个非负整数分别表示 $l1_1,l1_2 \ldots l1_n$。

第 $3$ 行 $n$ 个非负整数分别表示 $r1_1,r1_2 \ldots r1_n$。

第 $4$ 行 $n$ 个非负整数分别表示 $l2_1,l2_2 \ldots l2_n$。

第 $5$ 行 $n$ 个非负整数分别表示 $r2_1,r2_2 \ldots r2_n$。

第 $6$ 行 $n$ 个非负整数分别表示 $w_1,w_2 \ldots w_n$。

数据保证 $l1_i \leq r1_i,l2_i \leq r2_i$。

输出格式

输出 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 列的整数表示小 X 从 $(1,1)$ 到 $(i,j)$ 的最短路。

3
0 1 1
0 1 2
0 0 2
0 1 2
2 0 4

0 inf inf
inf -2 inf
inf 1 -4

10
0 1 1 2 2 2 3 3 3 3
0 1 2 2 3 3 3 4 4 4
0 1 2 2 3 3 3 3 4 4
0 1 2 3 4 4 5 5 5 5
8 4 2 1 2 4 8 4 2 1

0 inf inf inf inf inf inf inf inf inf
inf 18 inf inf inf inf inf inf inf inf
inf 15 20 18 inf inf inf inf inf inf
inf inf 18 16 inf inf inf inf inf inf
inf inf 12 10 8 9 12 7 4 2
inf inf 13 11 9 10 13 8 5 3
inf inf 16 14 12 13 16 11 8 6
inf inf 11 7 3 4 7 2 -1 -3
inf inf 8 4 0 1 4 -1 -4 -6
inf inf 6 2 -2 -1 2 -3 -6 -8

提示

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^3,0 \leq l1_i \leq r1_i \leq n,0 \leq l2_i \leq r2_i \leq n,0 \leq w_i \leq 10^5$ $,l1_i \leq r1_i < i,l2_i \leq r2_i < i$。

样例解释 #1:

• 从 $(1,1)$ 到 $(1,1)$ 显然要花费 $0$ 秒。

• 从 $(1,1)$ 可以直接到 $(2,2)$, 花费 $w_1 + w_1 + w_2 + w_2 - 1 - 1 - 2 - 2 = -2$ 秒。

• 从 $(1,1)$ 也可以直接到 $(3,2)$, 花费 $w_1 + w_1 + w_3 + w_2 - 1 - 1 - 3 - 2 = 1$ 秒。

• 要从 $(1,1)$ 到达 $(3,3)$，要先从 $(1,1)$ 到达 $(2,2)$，再从 $(2,2)$ 到达 $(3,3)$。花费 $w_1 + w_1 + w_2 + w_2 - 1 - 1 - 2 - 2 + w_2 + w_2 + w_3 + w_3 - 2 - 2 - 3 - 3 = -4$ 秒。

• 经过手算，可以发现，从 $(1,1)$ 不能到达其他位置。