Little N and Little O will participate in a grand programming contest, NOIP, in November 2022! Little P will serve as the judge for the competition. Little N and Little O each lead a team of $n$ people, and the contestants in each team are numbered from $1$ to $n$. Each contestant has a corresponding programming skill level. Specifically, in the team led by Little N, the programming skill level of the contestant numbered $i$ ($1 \le i \le n$) is $a_i$; in the team led by Little O, the programming skill level of the contestant numbered $i$ ($1 \le i \le n$) is $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 the fact that contestants participate in matches consecutively, Little P will choose two parameters $l, r$ ($1 \le l \le r \le n$), which means that all contestants from both teams with numbers in the range $[l, r]$ are invited to the venue to prepare for the match. At the venue, Little N and Little O will pick parameters $p, q$ ($l \le p \le q \le r$) by rolling dice, and only contestants with numbers in the range $[p, q]$ are eligible to compete. To provide the audience with the most exciting match, both teams will send the contestant with the highest programming skill level within the range $[p, q]$ to compete. Assuming the skill level of the contestant sent by Little N is $m_a$ and the skill level of the contestant sent by Little O is $m_b$, the excitement of the match is $m_a \times m_b$.

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

Input

The input is read from the file match.in.

The first line contains two positive integers $T$ and $n$, representing the test case 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$, representing the programming skill level of the contestant numbered $i$ in Little N's team.

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

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

The next $Q$ lines each contain two positive integers $l_i, r_i$, representing the parameters $l, r$ for the $i$-th match.

Output

The output is written to the file match.out.

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

Examples

Input 1

0 2
2 1
1 2
1
1 2

Output 1

8

Note 1

When $p = 1, q = 2$, Little N sends contestant 1, Little O sends contestant 2, and the match excitement is $2 \times 2 = 4$. When $p = 1, q = 1$, Little N sends contestant 1, Little O sends contestant 1, and the match excitement is $2 \times 1 = 2$. When $p = 2, q = 2$, Little N sends contestant 2, Little O sends contestant 2, and the match excitement is $1 \times 2 = 2$.

Example 2

See match/match2.in and match/match2.ans in the contestant directory. This sample satisfies the constraints for test cases 1–2.

Example 3

See match/match3.in and match/match3.ans in the contestant directory. This sample satisfies the constraints for test cases 3–5.

Subtasks

For all data, it is guaranteed that: $1 \le n, Q \le 2.5 \times 10^5$, $1 \le l_i \le r_i \le n$, $1 \le a_i, b_i \le n$, and $\{a_i\}$ and $\{b_i\}$ each form a permutation of $1$ to $n$.

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