Teleportation and Time Travel

In City Z, the city is structured as an \(n \times n\) matrix. Small X starts at cell \((1,1)\) and wants to reach various dinner parties by using a teleportation device combined with a time‐travel machine. The teleportation from a cell \((p,q)\) to a cell \((x,y)\) (with \(1 \le x,y \le n\)) is only allowed if the destination comes with its own parameters \(l1_x, r1_x, l2_y, r2_y\) (which satisfy \(0\le l1_x\le r1_x < x\) and \(0\le l2_y\le r2_y < y\)). In other words, you can teleport to \((x,y)\) from any cell \((p,q)\) provided that \[ l1_x \le p \le r1_x \quad \text{and} \quad l2_y \le q \le r2_y. \]

The cost of teleporting from \((p,q)\) to \((x,y)\) is given by \[ w_p + w_q + w_x + w_y - p - q - x - y,\] where \(w_i\) is the weight associated with row \(i\) and similarly \(w_j\) is the weight associated with column \(j\). (Note that because of the time–travel machine the cost can sometimes be negative.) Also, if any teleportation results in a cell whose coordinates are not positive integers, the machine will break.

Initially, only cell \((1,1)\) is reached (with time cost 0) and no direct move is allowed between cells unless a teleportation is performed. For every \((x,y)\) with \(1\le x,y\le n\), if there exists a sequence of teleports from \((1,1)\) reaching \((x,y)\), output the minimum total time needed; otherwise, output inf.

Note on the Teleportation Parameters

• The input provides an integer \(n\) as the grid size.
• The next two lines contain \(n\) integers each: the first array gives the row weights \(w_1, w_2, \ldots, w_n\) and the second gives the column weights \(w_1, w_2, \ldots, w_n\).
• For every cell \((x,y)\) with \(2\le x,y\le n\) (in row-major order), you are given four integers: \(l1_x, r1_x, l2_y, r2_y\). A teleportation from a cell \((p,q)\) to \((x,y)\) is possible if \(p\) and \(q\) satisfy \[ l1_x \le p \le r1_x \quad \text{and} \quad l2_y \le q \le r2_y.\] (By the constraints, note that \(r1_x < x\) and \(r2_y < y\)).

The cost to move from \((p,q)\) to \((x,y)\) is computed as \[ \bigl(w_p - p\bigr) + \bigl(w_q - q\bigr) + \bigl(w_x - x\bigr) + \bigl(w_y - y\bigr).\]

inputFormat

The first line contains an integer \(n\) (the size of the matrix).

The second line contains \(n\) space‐separated integers: \(w_1, w_2, \ldots, w_n\) (the row weights).

The third line contains \(n\) space‐separated integers: \(w_1, w_2, \ldots, w_n\) (the column weights).

Then, for every cell \((x,y)\) with \(2\le x,y\le n\) (iterated in row-major order, i.e. for \(x=2\) to \(n\) and within that for \(y=2\) to \(n\)), there is a line containing four space‐separated integers: l1_x r1_x l2_y r2_y, which satisfy \(0\le l1_x\le r1_x < x\) and \(0\le l2_y \le r2_y < y\).

outputFormat

Output \(n\) lines. The \(i\)\(-th\) line should contain \(n\) space‐separated tokens. For cell \((x,y)\), output the minimum total time required to reach that cell from \((1,1)\) using the teleportation moves. If the cell is unreachable, output inf instead.

sample

3
1 2 3
1 2 3
1 1 1 1
1 1 1 2
1 2 1 1
1 2 1 2

0 inf inf
inf 0 0
inf 0 0