题目描述

小 $Q$ 在玩一个策略游戏。给定两个正整数数组

• 长度为 $n$ 的数组 $A$，元素两两不同；

• 长度为 $m$ 的数组 $B$，元素两两不同。

据此定义一个 $n \times m$ 的矩阵 $C$，其元素 C[i][j]=A[i]×B[j] （所有下标均从 $1$ 开始）。

游戏中有一个固定的子矩阵大小 $r$×$r$。小 $Q$ 需要在矩阵 $C$ 中“选一个” $r$×$r$ 的子矩阵，使得该子矩阵中的最大值尽可能小。

具体地：

• 令 $s$, $t$ 满足 1≤s≤n−r+1

  1≤t≤m−r+1

• 该 $r \times r$ 子矩阵的所有元素为 C[s+i−1][t+j−1],1≤i≤r, 1≤j≤r

• 子矩阵的“最大值”记作
  M(s,t)=max{C[s+i−1][t+j−1]∣1≤i,j≤r}

• 小 $Q$ 要在所有合法的 $(s, t)$ 中，选出使 $M(s, t)$ 最小的那个 $(s, t)$。

接着，他要回答 $q$ 次询问。每次询问给出两个整数 $x$, $y$，表示固定让 $s = x$，$t = y$（且保证 $1 \le x \le n - r + 1$，$1 \le y \le m - r + 1$），问这块子矩阵的最大值 $M(x, y)$ 是多少。

输入格式

n m r q
A[1] A[2] … A[n]
B[1] B[2] … B[m]
x₁ y₁
x₂ y₂
…
x_q y_q

输出格式

共 $q$ 行，第 $k$ 行输出第 $k$ 轮游戏在双方最优策略下的得分（一个整数）。

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

0
4

6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3

0
-2
3
2
-1

数据规模与约定

$1 \le n, m \le 10^5$

$1 \le r \le \min(n, m)$

$1 \le q \le 10^5$

$1 \le A[i], B[j] \le 10^4$（两两不同）

对每个查询 $(x, y)$ 保证：

1≤x≤n−r+1

1≤y≤m−r+1

时间限制：$2.0\text{s}$

内存限制：$512\text{MB}$