뗏목 제작

울창한 두 숲 KOI 숲과 IOI 숲에는 많은 나무들이 우거져 있다. KOI 숲에는 $0$번부터 $N-1$번까지, 총 $N$개의 나무가 왼쪽에서 오른쪽으로 일렬로 줄지어 있으며, IOI 숲에는 $0$번부터 $M-1$번까지 총 $M$개의 나무가 같은 방식으로 일렬로 줄지어 있다. KOI 숲의 $i$ ($0 \le i \le N-1$)번 나무의 높이는 $A\[i]$, IOI 숲의 $j$ ($0 \le j \le M-1$)번 나무의 높이는 $B\[j]$이다.

당신의 부족은 외딴 섬에서 바다의 신께 기도를 드리는 오랜 전통을 가지고 있으며, 그 의식을 치르기 위해 뗏목을 만들어야 한다. 당신은 두 숲에서 나무를 벌목하여 뗏목을 제작하기로 하였다.

뗏목을 타고 섬까지 가는 것은 매우 위험하기 때문에, 당신은 뗏목을 최대한 안정적으로 만들고자 한다. 뗏목은 나무들을 옆으로 이어붙여 만들며, 그 안에 포함되는 직사각형 모양의 면적이 클수록 안정적이다. 구체적으로, 뗏목을 구성하는 나무의 높이가 왼쪽에서부터 $H\[0], H\[1], \ldots, H\[L-1]$이라고 할 때, 뗏목의 안정성은

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

의 값으로 정의된다. 즉, 가능한 모든 연속된 구간 $\[s, l]$에 대해 그 구간에 포함되는 나무들의 최소 높이를 구하고, 그 높이에 구간 너비인 $(l-s+1)$를 곱했을 때의 최댓값을 의미한다.

부족의 전통에 따라, 뗏목을 구성하는 나무들은 다음과 같은 규칙을 따라야 한다.

1. 벌목한 나무는 모두 뗏목에 사용해야 한다.
2. KOI 숲에서 잘라온 나무들은 원래 숲 내에서의 순서를 유지해야 한다. 즉, 원래 숲에서 나무 $X$가 나무 $Y$보다 왼쪽에 있었다면, 뗏목에서도 $X$가 $Y$보다 왼쪽에 있어야 한다.
3. IOI 숲에서 잘라온 나무들도 마찬가지로 원래 순서를 유지해야 한다.

KOI 숲의 나무들은 $0$번부터 $N-1$번까지 $N$그루 모두를 모두 벌목하기로 결정되었다. 그러나, IOI 숲에서 어떤 나무들을 벌목할지는 아직 결정되지 않았다. 당신은 $0$부터 $Q-1$ 까지 번호 붙여진 $Q$개 질의에 답해야 한다. 질의들은 길이 $Q$의 배열 $L$과 $R$로 표현된다. 질의 $k(0 \le k \le Q-1)$의 답은 IOI 숲에서 번호가 $L\[k]$ 이상 $R\[k]$ 이하인 나무들을 벌목하는 경우 얻을 수 있는 뗏목의 가능한 최대 안정성이다.

• $1 \le N, M \le 150\\,000$
• $1 \le Q \le 500\\,000$
• 모든 $0 \le i \le N - 1$ 에 대해 $1 \le A\[i] \le 10^9$
• 모든 $0 \le j \le M - 1$ 에 대해 $1 \le B\[j] \le 10^9$
• 모든 $0 \le k \le Q - 1$ 에 대해 $0 \le L\[k] \le R\[k] \le M - 1$