Background

After traveling a long distance in City Z, Xiao X is going to attend someone else's banquet.

Problem Description

City Z is an $n \times n$ matrix. Xiao X plans to reach the banquet using only a teleporter and a time-space traveler. If Xiao X is currently at position $(p,q)$ satisfying $l1_x \le p \le r1_x$ and $l2_y \le q \le r2_y$ $(0 \le l1_x \le r1_x < x,0 \le l2_y \le r2_y < y)$, then Xiao X can reach position $(x,y)$.

However, because the teleport technology is not very mature and due to the influence of the time-space traveler, each teleport costs $w_p+w_q+w_x+w_y-p-q-x-y$ seconds (because of the nature of the time-space traveler, the time may be negative). If an index is not a positive integer, the teleporter will be damaged, so Xiao X can only reach positions whose indices are all positive integers.

Now Xiao X is at $(1,1)$. He wants to attend the banquet, but he does not know where it is. So he wants you to compute the minimum time needed to reach every position $(x,y)$ $(1 \le x,y \le n)$. If a position cannot be reached, output inf.

Input Format

Line $1$ contains an integer $n$, the size of the matrix.

Line $2$ contains $n$ non-negative integers: $l1_1,l1_2 \ldots l1_n$.

Line $3$ contains $n$ non-negative integers: $r1_1,r1_2 \ldots r1_n$.

Line $4$ contains $n$ non-negative integers: $l2_1,l2_2 \ldots l2_n$.

Line $5$ contains $n$ non-negative integers: $r2_1,r2_2 \ldots r2_n$.

Line $6$ contains $n$ non-negative integers: $w_1,w_2 \ldots w_n$.

The testdata guarantees that $l1_i \le r1_i$ and $l2_i \le r2_i$.

Output Format

Output $n$ lines, each containing $n$ integers. The integer in row $i$ and column $j$ denotes the shortest path length from $(1,1)$ to $(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

Hint

This problem uses bundled testcases.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^3$, $0 \le l1_i \le r1_i \le n$, $0 \le l2_i \le r2_i \le n$, $0 \le w_i \le 10^5$, and $l1_i \le r1_i < i$, $l2_i \le r2_i < i$.

Sample Explanation #1:

• From $(1,1)$ to $(1,1)$ obviously takes $0$ seconds.

• From $(1,1)$ you can directly reach $(2,2)$, costing $w_1 + w_1 + w_2 + w_2 - 1 - 1 - 2 - 2 = -2$ seconds.

• From $(1,1)$ you can also directly reach $(3,2)$, costing $w_1 + w_1 + w_3 + w_2 - 1 - 1 - 3 - 2 = 1$ seconds.

• To reach $(3,3)$ from $(1,1)$, you need to go from $(1,1)$ to $(2,2)$ first, then from $(2,2)$ to $(3,3)$. The cost is $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$ seconds.

• By manual calculation, you can find that from $(1,1)$ you cannot reach any other position.

Translated by ChatGPT 5