Problem Description

Xiao N and Xiao O will participate in a grand programming competition, NOIP, in November 2022! Xiao P will serve as the referee to host the competition. Xiao N and Xiao O each lead a team of $n$ individuals, with players numbered from $1$ to $n$ within each team. Each player has a corresponding programming skill level. Specifically, in Xiao N's team, the player numbered $i$ ($1 \leq i \leq n$) has a programming skill level of $a_i$; in Xiao O's team, the player numbered $i$ ($1 \leq i \leq n$) has a programming skill level of $b_i$. Notably, $\{a_i\}$ and $\{b_i\}$ are permutations of the numbers from $1$ to $n$.

Before each match, considering travel distance and consecutive participation, Xiao P will select two parameters $l, r$ ($1 \leq l \leq r \leq n$), indicating that the match will invite all players from both teams whose numbers fall within the range $[l, r]$ to the venue. At the venue, Xiao N and Xiao O will roll dice to select parameters $p, q$ ($l \leq p \leq q \leq r$), and only players whose numbers fall within the range $[p, q]$ can compete. To provide the most exciting match for the audience, both teams will send the player within the range $[p, q]$ with the highest programming skill level to compete. Assuming the skill level of the player sent by Xiao N is $m_a$ and the skill level of the player sent by Xiao O is $m_b$, the excitement level of the match is $m_a \times m_b$.

NOIP has a total of $Q$ matches, and the parameters $l, r$ for each match have been determined, but $p, q$ have not been drawn. Xiao P wants to know, for each match, the sum of the excitement levels of all possible matches under the parameters $p, q$ ($l \leq p \leq q \leq r$). Since the answer may be very large, you only need to output the result modulo $2^{64}$ for each match.

Input Format

The first line contains two positive integers $T, n$, representing the test point number and the number of participants, respectively. If the data is a sample, it is guaranteed that $T = 0$.

The second line contains $n$ positive integers, where the $i$-th integer is $a_i$, indicating the programming skill level of the player numbered $i$ in Xiao N's team.

The third line contains $n$ positive integers, where the $i$-th integer is $b_i$, indicating the programming skill level of the player numbered $i$ in Xiao O's team.

The fourth line contains a positive integer $Q$, indicating the number of matches.

The next $Q$ lines, the $i$-th line contains two positive integers $l_i, r_i$, indicating the parameters $l, r$ for the $i$-th match.

Output Format

Output $Q$ lines, where the $i$-th line contains a non-negative integer, indicating the sum of the excitement levels of all possible matches for the $i$-th match modulo $2^{64}$.

Sample Input and Output

Input Sample #1

0 2
2 1
1 2
1
1 2

Output Sample #1

8

Input Sample #2

See the file in the attachment match/match2.in.

Output Sample #2

See the file in the attachment match/match2.ans.

Input Sample #3

See the file in the attachment match/match3.in.

Output Sample #3

See the file in the attachment match/match3.ans.

Notes/Hints

[Sample 1 Explanation]

When $p = 1, q = 2$, Xiao N will send player number $1$, and Xiao O will send player number $2$, the excitement level of the match is $2 \times 2 = 4$.

When $p = 1, q = 1$, Xiao N will send player number $1$, and Xiao O will send player number $1$, the excitement level of the match is $2 \times 1 = 2$.

When $p = 2, q = 2$, Xiao N will send player number $2$, and Xiao O will send player number $2$, the excitement level of the match is $1 \times 2 = 2$.

[Sample 2]

This sample meets the constraints of test points $1 \sim 2$.

[Sample 3]

This sample meets the constraints of test points $3 \sim 5$.

[Data Range]

For all data, it is guaranteed that: $1 \leq n, Q \leq 2.5 \times 10^5$, $1 \leq l_i \leq r_i \leq n$, $1 \leq a_i, b_i \leq n$ and $\{a_i\}$ and $\{b_i\}$ are permutations of the numbers from $1$ to $n$.

Special Property A: It is guaranteed that $a$ is a uniformly randomly generated permutation of $1 \sim n$.

Special Property B: It is guaranteed that $b$ is a uniformly randomly generated permutation of $1 \sim n$.

见题面 Input 部分

见题面 Output 部分