There are many trees in two lush forests: the KOI forest and the IOI forest. In the KOI forest, there are a total of $N$ trees, numbered from $0$ to $N-1$, lined up in a row from left to right. In the IOI forest, there are a total of $M$ trees, numbered from $0$ to $M-1$, also lined up in a row in the same manner. The height of the $i$-th tree ($0 \le i \le N-1$) in the KOI forest is $A[i]$, and the height of the $j$-th tree ($0 \le j \le M-1$) in the IOI forest is $B[j]$.

Your tribe has an ancient tradition of praying to the sea god on a remote island, and you must build a raft to perform the ritual. You have decided to build the raft by logging trees from the two forests.

Since traveling to the island on a raft is very dangerous, you want to make the raft as stable as possible. A raft is made by joining trees side by side, and it is more stable if the area of the rectangular shape contained within it is larger. Specifically, if the heights of the trees constituting the raft are $H[0], H[1], \dots, H[L-1]$ from left to right, the stability of the raft is defined as the value:

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

In other words, it is the maximum value obtained by finding the minimum height of the trees in every possible contiguous segment $[s, l]$ and multiplying that height by the segment width $(l - s + 1)$.

According to the tribe's tradition, the trees constituting the raft must follow these rules:

1. All logged trees must be used for the raft.
2. Trees cut from the KOI forest must maintain their original order within the forest. That is, if tree $X$ was to the left of tree $Y$ in the original forest, $X$ must also be to the left of $Y$ on the raft.
3. Trees cut from the IOI forest must also maintain their original order.

It has been decided that all $N$ trees from the KOI forest, from $0$ to $N-1$, will be logged. However, it has not yet been decided which trees from the IOI forest will be logged. You must answer $Q$ queries, numbered from $0$ to $Q-1$. The queries are represented by arrays $L$ and $R$ of length $Q$. The answer to query $k$ ($0 \le k \le Q-1$) is the maximum possible stability of the raft that can be obtained when logging the trees in the IOI forest with indices from $L[k]$ to $R[k]$ inclusive.

Implementation Details

You must implement the following function:

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

• $A$: An integer array of size $N$.
• $B$: An integer array of size $M$.
• $L, R$: Integer arrays of size $Q$.
• This function returns an integer array of size $Q$.
• Let the returned integer array be $C$. For an integer $k$ such that $0 \le k \le Q-1$, $C[k]$ is the maximum possible stability of the raft when logging all trees from the KOI forest and the trees from the IOI forest with indices between $L[k]$ and $R[k]$ inclusive.
• This function is called exactly once per test case.
• You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $1 \le N, M \le 150\,000$
• $1 \le Q \le 500\,000$
• $1 \le A[i] \le 10^9$ for all $0 \le i \le N-1$
• $1 \le B[j] \le 10^9$ for all $0 \le j \le M-1$
• $0 \le L[k] \le R[k] \le M-1$ for all $0 \le k \le Q-1$

Subtasks

1. (10 points) $N, M, Q \le 3\,000$
2. (8 points) $Q \le 300$
3. (20 points) For all $0 \le k \le Q-1$, the following two conditions hold:
   • $L[k] = 0$ or $B[L[k] - 1] < \min(B[L[k]], B[L[k] + 1], \dots, B[R[k]])$
   • $R[k] = M - 1$ or $B[R[k] + 1] < \min(B[L[k]], B[L[k] + 1], \dots, B[R[k]])$
4. (6 points) $A[i] \le 50$ for all $0 \le i \le N-1$, and $B[j] \le 50$ for all $0 \le j \le M-1$
5. (14 points) $A[i]$ is constant for all $0 \le i \le N-1$
6. (11 points) $B[j] \ge B[j+1]$ for all $0 \le j \le M-2$
7. (13 points) $L[k] = 0$ for all $0 \le k \le Q-1$
8. (7 points) $R[k] - L[k]$ is the same for all $0 \le k \le Q-1$
9. (11 points) No additional constraints.

Examples

Input 1

5 4 2
3 3 1 6 1
3 5 7 6
0 0
1 3

Output 1

12
20

Note 1

For $L[0] = 0, R[0] = 1$, the maximum stability is 12. One way to achieve this is: * Construct the raft with KOI trees 0, 1, then IOI trees 0, 1, then KOI trees 2, 3, 4. The heights are $H = [3, 3, 3, 5, 1, 6, 1]$. Since $\min(H[0], H[1], H[2], H[3]) = 3$, the stability is $3 \times 4 = 12$.

For $L[0] = 0, R[0] = 3$, the maximum stability is 20. One way to achieve this is: * Construct the raft with KOI trees 0, 1, 2, then IOI trees 0, 1, 2, 3, then KOI trees 3, 4. The heights are $H = [3, 3, 1, 3, 5, 7, 6, 6, 1]$. Since $\min(H[4], H[5], H[6], H[7]) = 5$, the stability is $5 \times 4 = 20$.

Input 2

5 8 8
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

Output 2

45
45
45
45
45
45
45
49

Input 3

3 2 1
1000000000 1000000000 1000000000
1000000000 1000000000
0 1

Output 3

5000000000