Little N and Little O will participate in a grand programming competition in November 2022, the NOIP!

Little P will preside over the competition as a referee.

Little N and little O each lead a team of ~n~ people, with players numbered from ~1~ to ~n~ in each team. Each player has a corresponding programming level. Specifically, in the team led by little N, the programming level of the player numbered ~i~ ~(1 \leq i \leq n)~ is ~a_i~; in the team led by little O, the programming level of the player numbered ~i~ (~1 \leq i \leq n~) is ~b_i~. Furthermore, each of ~\{a_i\}~ and ~\{b_i\}~ forms a permutation of ~1~ to ~n~.

Before each game, Little P will choose two parameters ~l~, ~r~ ~(1 \leq l \leq r \leq n)~, which means that the members of this game will be chosen from all players in the range ~[l, r]~ on both teams. Little N and Little O will then select parameters ~p~, ~q~ ~(l \leq p \leq q \leq r)~ by rolling dice, and only players whose numbers belong to ~[p,q]~ can participate. In order to provide the audience with the most exciting game, both teams will send their player whose number is in ~[p,q]~ that has the highest programming level to participate in the game. Assuming that the level of the player sent by little N is ~m_a~, and the level of the player sent by little O is ~m_b~, then the excitement level of the game is ~m_a \times m_b~.

There are a total of ~Q~ games in NOIP, and the parameters ~l~ and ~r~ of each game have been determined, but ~p~ and ~q~ have not been extracted yet. Little P wants to know, for each game, the sum of the excitement values of the game under all possible 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 game.

Input Specification

The first line contains two positive integers ~T~ and ~n~, which respectively represent the test case number and the number of participants. Samples will have ~T=0~.

The second line contains ~n~ positive integers, the ~i~-th integer being ~a_i~, which represents the programming level of player number ~i~ in Little N's team.

The third line contains ~n~ positive integers, the ~i~-th integer being ~b_i~, which represents the programming level of player number ~i~ in Little O's team.

The fourth line contains a positive integer ~Q~, indicating the number of games played.

In the next ~Q~ line, line ~i~ contains two positive integers ~l_i~, ~r_i~, representing the parameters ~l~, ~r~ of the ~i~-th match.

Output Specification

Output Q lines, the ~i~-th line should contain a non-negative integer, which represents the result, modulo ~2^{64}~, of the sum of excitement values of all possible games in the ~i~-th round.

Sample Input 1

0 2
2 1
1 2
1
1 2

Sample Output 1

8

Explanation of Sample 1

• When ~p=1~, ~q=2~, Little N will send player No. 1, and Little O will send player No. 2. The excitement is ~2 \times 2 = 4~.
• When ~p=1~, ~q=1~, Little N will send player No. 1, and Little O will send player No. 1. The excitement is ~2 \times 1 = 2~.
• When ~p=2~, ~q=2~, Little N will send player No. 2, and Little O will send player No. 2, and excitement is ~1 \times 2 = 2~.

Additional Samples

Additional sample cases can be found here.

• The second case satisfies the constraints of cases 1-2.
• The third case satisfies the constraints of cases 3-5.

Constraints

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

Case	~n \leq~	~Q \leq~	~a~ random	~b~ random
~1, 2~	~30~	~30~	yes	yes
~3, 4, 5~	~3000~	~3000~
~6, 7~	~10^5~	~5~
~8, 9~	~2.5 \times 10^5~
~10, 11~	~10^5~		no	no
~12, 13~	~2.5 \times 10^5~
~14, 15~	~10^5~	~10^5~	yes	yes
~16, 17~	~2.5 \times 10^5~	~2.5 \times 10^5~
~18, 19~	~10^5~	~10^5~		no
~20, 21~	~2.5 \times 10^5~	~2.5 \times 10^5~
~22, 23~	~10^5~	~10^5~	no
~24, 25~	~2.5 \times 10^5~	~2.5 \times 10^5~