P9550 「PHOI-1」晚宴筵

小 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)$ 的最短路。

**本题采用捆绑测试。** | Subtask | $n$ | $l1_i,l2_i$ | $w_i$ | 分值 | | :-: | :-: | :-: | :-: | :-: | | $0$ | $1 \le n \le 70$ | 无特殊限制 | $i \leq w_i \leq 10^5(1 \leq i \leq n)$ | $15$ | | $1$ | $1 \le n \le 70$ | 无特殊限制 | 无特殊限制 | $25$ | | $2$ | 无特殊限制 | $l1_i=l2_i=r1_i=r2_i=1(2\le i \le n)$ | 无特殊限制 | $5$ | | $3$ | 无特殊限制 | 无特殊限制 | 无特殊限制 | $55$ | 对于 $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)$ 不能到达其他位置。