有两行森林。第一行森林有 $N$ 棵树，从左到右依次编号为 $0$ 到 $N-1$。第二行森林有 $M$ 棵树，同样从左到右编号为 $0$ 到 $M-1$。第一行森林中第 $i$ $(0 \leq i \leq N-1)$ 棵树的高度是 $A[i]$，第二行森林中第 $j$ $(0 \leq j \leq M-1)$ 棵树的高度是 $B[j]$。

你想要制作一个木筏，材料将从这两片森林中砍伐而来。假设木筏由左至右的树高依次为 $H[0], H[1], \ldots, H[L-1]$，其稳定性定义为：

$$ \max_{0 \leq s \leq l \leq L-1} (\min(H[s], \ldots, H[l]) \times (l - s + 1)) $$

木筏的树木必须遵循以下规则：

1. 砍伐的所有树都要用于木筏。
2. 从第一行森林砍来的树必须保持原有顺序，即如果树 $X$ 在森林中位于树 $Y$ 左侧，那么在木筏上 $X$ 也必须在 $Y$ 左侧。
3. 从第二行森林砍来的树同样需保持原有顺序。

你决定砍伐第一行森林中从 $0$ 到 $N-1$ 的全部 $N$ 棵树，但第二行森林中具体砍哪些树尚未确定。你需要回答 $Q$ 个编号从 $0$ 到 $Q-1$ 的问题，这些问题由长度为 $Q$ 的数组 $L$ 和 $R$ 表示。第 $k$ $(0 \leq k \leq Q-1)$ 个问题是：若从第二行森林砍伐编号在 $L[k]$ 到 $R[k]$ 之间的树，木筏的最大稳定性是多少？

实现细节

你需要实现以下函数：

std::vector<long long> max_stability(std::vector<int> A, std::vector<int> B,
std::vector<int> L, std::vector<int> R)

• A：长度为 $N$ 的整数数组，表示 KOI 森林树高。
• B：长度为 $M$ 的整数数组，表示 IOI 森林树高。
• L, R：长度为 $Q$ 的整数数组，表示每次询问的范围。
• 函数需返回一个长度为 $Q$ 的整数数组 $C$，其中对于 $0 \leq k \leq Q-1$，$C[k]$ 表示用 KOI 森林所有树及 IOI 森林编号从 $L[k]$ 到 $R[k]$ 的树制作木筏时，可能的最大稳定性。
• 每个测试用例中，该函数只被调用一次。

你提交的代码不得包含任何输入输出函数。

样例一

假设 $N=5$，$M=4$，$Q=2$，$A=[3,3,1,6,1]$，$B=[3,5,7,6]$，$L=[0,0]$，$R=[1,3]$。

评测程序调用：

max_stability([3, 3, 1, 6, 1], [3, 5, 7, 6], [0, 0], [1, 3])

• 当 $L[0]=0, R[0]=1$ 时，最大稳定性为 $12$。例如：

  • 木筏从左到右依次为 KOI 的 $0$、$1$ 号树，IOI 的 $0$、$1$ 号树，KOI 的 $2$、$3$、$4$ 号树，高度为 $H=[3,3,3,5,1,6,1]$。
  • 取 $[0, 3]$，最小高度 $\min(H[0], H[1], H[2], H[3]) = 3$，宽度 $4$，稳定性 $3 \times 4 = 12$。

• 当 $L[1]=0, R[1]=3$ 时，最大稳定性为 $20$。例如：

  • 木筏从左到右依次为 KOI 的 $0$、$1$、$2$ 号树，IOI 的 $0$、$1$、$2$、$3$ 号树，KOI 的 $3$、$4$ 号树，高度为 $H=[3,3,1,3,5,7,6,6,1]$。
  • 取 $[4, 7]$，最小高度 $\min(H[4], H[5], H[6], H[7]) = 5$，宽度 $4$，稳定性 $5 \times 4 = 20$。

函数应返回 $[12, 20]$。

样例二

评测程序调用：

max_stability([9, 9, 9, 9, 9], [1, 2, 3, 4, 5, 6, 7, 8], [0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7])

函数应返回 $[45, 45, 45, 45, 45, 45, 45, 49]$。

样例三

评测程序调用：

max_stability([1000000000, 1000000000, 1000000000], [1000000000, 1000000000], [0], [1])

函数应返回 $[5000000000]$。

子任务

对于所有输入数据，满足：

• $1 \leq N, M \leq 150000$
• $1 \leq Q \leq 500000$
• 对于所有 $0 \leq i \leq N-1$，$1 \leq A[i] \leq 10^{9}$
• 对于所有 $0 \leq j \leq M-1$，$1 \leq B[j] \leq 10^{9}$
• 对于所有 $0 \leq k \leq Q-1$，$0 \leq L[k] \leq R[k] \leq M-1$

详细子任务附加限制及分值如下表所示。

样例交互库

示例评测程序接收以下格式的输入：

• 第 $1$ 行：$N\ M\ Q$
• 第 $2$ 行：$A[0]\ A[1]\ \ldots\ A[N-1]$
• 第 $3$ 行：$B[0]\ B[1]\ \ldots\ B[M-1]$
• 第 $4+k$ $(0 \leq k \leq Q-1)$ 行：$L[k]\ R[k]$

输出格式如下：

• 第 $1+k$ $(0 \leq k \leq Q-1)$ 行：设 max_stability 返回值为 $C$，则输出 $C[k]$

请注意，示例评测程序可能与实际评测程序有所不同。