410009: GYM103896 K Fish Exercise

Pesky the Fish has been one the player's favorite pets. However, after a losing streak, the player threatens to turn Pesky into the Sushi item on Turn 9 if they lose another game! To prevent this, Pesky starts training on an obstacle course.

The obstacle course can be described as an $$$n \times n$$$ grid, where each row and each column is numbered from $$$1$$$ to $$$n$$$. Each row is also assigned some value $$$x_i$$$, and each column is assigned some value $$$y_i$$$. To move around in the obstacle course, Pesky can either move horizontally or vertically. If Pesky moves horizontally, the difficulty of the path can be represented by the product of:

• the value of the row,
• the distance traveled,
• and sum of the start and end column values.

Similarly, if Pesky moves vertically, the difficulty of the path is the product of:

• the value of the column,
• the distance traveled,
• and sum of the start and end row values.

In other words, the difficulties can be represented by the formulas below:

• Horizontal Move $$$(r, c_1) \to (r, c_2)$$$: $$$x_r \cdot |c_1 - c_2| \cdot (y_{c_1} + y_{c_2})$$$
• Vertical Move $$$(r_1, c) \to (r_2, c)$$$: $$$y_c \cdot |r_1 - r_2| \cdot (x_{r_1} + x_{r_2})$$$

Pesky must do $$$q$$$ swims, in which Pesky starts at the start $$$(r_1, c_1)$$$ and chooses a series of moves until it reaches the end $$$(r_2, c_2)$$$. Though the stakes are high, Pesky is lazy, so it wants to find a path where the maximum difficulty across all moves is minimized. For each of these swims, can you determine the minimum possible value of the maximum difficulty?

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^3$$$): the height and length of the square grid.

The next line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^5$$$): the values of each row.

The next line contains $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$1 \leq y_i \leq 10^5$$$): the values of each column.

The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$): the number of queries.

The following $$$q$$$ lines contain four integers $$$r_1, c_1, r_2, c_2$$$ ($$$1 \leq r_1, c_1, r_2, c_2 \leq n, (r_1, c_1) \neq (r_2, c_2)$$$). $$$(r_1, c_1)$$$ is the start position, and $$$(r_2, c_2)$$$ is the end position.

For each of the $$$q$$$ queries, print a single integer: the minimum possible value of the maximum difficulty on any sequence of moves from the start to the end.

2
1 1
1 100
3
1 1 1 2
1 1 2 1
1 1 2 2

101
2
101

5
1 10 100 1 100
1 100 10 1 100
5
1 1 5 5
5 4 5 3
1 2 1 3
4 1 4 4
1 4 5 4

10100
1010
101
6
101