Description

Xiao N and Xiao O will take part in the grand programming contest NOIP in November 2022, and Xiao P will serve as the judge. Xiao N and Xiao O each lead a team of $n$ people, and players in each team are numbered from $1$ to $n$. Every player has a programming skill level. Specifically, in Xiao N's team, the player with index $i$ ($1 \leq i \leq n$) has skill level $a _ i$; in Xiao O's team, the player with index $i$ ($1 \leq i \leq n$) has skill level $b _ i$. In particular, $\{a _ i\}$ and $\{b _ i\}$ each form a permutation of $1$ to $n$.

Before each match, considering factors such as travel distance and players competing in consecutive matches, Xiao P chooses two parameters $l, r$ ($1 \leq l \leq r \leq n$), meaning that for this match all players whose indices are in $[l, r]$ from both teams will come to the venue to get ready. At the venue, Xiao N and Xiao O will pick parameters $p, q$ by rolling dice ($l \leq p \leq q \leq r$), and only players with indices in $[p, q]$ are eligible to compete. To deliver the most exciting match to the audience, both teams will send the player with the maximum programming skill value whose index lies in $[p, q]$. Suppose Xiao N sends a player with skill $m _ a$, and Xiao O sends a player with skill $m _ b$; then the excitement of the match is $m _ a \times m _ b$.

There are $Q$ matches in total in NOIP. For each match, the parameters $l, r$ are fixed, but $p, q$ have not yet been drawn. Xiao P wants to know, for each match, the sum of the excitement values over all possible choices of $p, q$ ($l \leq p \leq q \leq r$). Since the answer can be very large, for each match you only need to output the result modulo $2 ^ {64}$.

Input Format

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

The second line contains $n$ positive integers; the $i$-th integer is $a _ i$, the programming skill level of the player with index $i$ in Xiao N's team.

The third line contains $n$ positive integers; the $i$-th integer is $b _ i$, the programming skill level of the player with index $i$ in Xiao O's team.

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

Each of the next $Q$ lines contains two positive integers $l _ i, r _ i$, the parameters $l, r$ for the $i$-th match.

Output Format

Output $Q$ lines. The $i$-th line should contain a non-negative integer, which is the sum of the excitement values over all possible matches for the $i$-th query, modulo $2 ^ {64}$.

0 2
2 1
1 2
1
1 2

8

见附件下的 match/match2.in。

见附件下的 match/match2.ans。

见附件下的 match/match3.in。

见附件下的 match/match3.ans。

Hint

【Sample 1 Explanation】

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

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

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

【Sample 2】

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

【Sample 3】

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

【Constraints】

For all testdata, 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\}$ each form a permutation of $1$ to $n$.

::cute-table{tuack} | Test points | $n$ | $Q$ | Special property A | Special property B | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1, 2$ | $\leq 30$ | $\leq 30$ | Yes | Yes | | $3, 4, 5$ | $\leq 3,000$ | $\leq 3,000$ | ^ | ^ | | $6, 7$ | $\leq 10 ^ 5$ | $\leq 5$ | ^ | ^ | | $8, 9$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | ^ | | $10, 11$ | $\leq 10 ^ 5$ | ^ | No | No | | $12, 13$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | ^ | | $14, 15$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | Yes | Yes | | $16, 17$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | | $18, 19$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | ^ | No | | $20, 21$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ | | $22, 23$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | No | ^ | | $24, 25$ | $\leq 2.5 \times 10 ^ 5$ | $\leq 2.5 \times 10 ^ 5$ | ^ | ^ |

Special property A: It is guaranteed that $a$ is a uniformly random permutation of $1 \sim n$.

Special property B: It is guaranteed that $b$ is a uniformly random permutation of $1 \sim n$.

Translated by ChatGPT 5