小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 $n$ 个人的队伍，选手在每支队伍内都是从 $1$ 到 $n$ 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 $i$（$1\le i\le n$）的选手的程序设计水平为 $a_i$；小 O 率领的队伍中，编号为 $i$（$1\le i\le n$）的选手的程序设计水平为 $b_i$。特别地，$\{a_i\}$ 和 $\{b_i\}$ 还分别构成了从 $1$ 到 $n$ 的排列。

每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数 $l,r$（$1\le l\le r\le n$），表示这一场比赛会邀请两队中编号属于 $[l,r]$ 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 $p,q$（$l\le p\le q\le r$），只有编号属于 $[p,q]$ 的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号在 $[p,q]$ 内的、程序设计水平值最大的选手参加比赛。假定小 N 派出的选手水平为 $m_a$，小 O 派出的选手水平为 $m_b$，则比赛的精彩程度为 $m_a\times m_b$。

NOIP 总共有 $Q$ 场比赛，每场比赛的参数 $l,r$ 都已经确定，但是 $p,q$ 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 $p,q$（$l\le p\le q\le r$）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 $2^{64}$ 取模的结果即可。

输入格式

第一行包含两个正整数 $T,n$，分别表示测试点编号和参赛人数。如果数据为样例则保证 $T=0$。

第二行包含 $n$ 个正整数，第 $i$ 个正整数为 $a_i$，表示小 N 队伍中编号为 $i$ 的选手的程序设计水平。

第三行包含 $n$ 个正整数，第 $i$ 个正整数为 $b_i$，表示小 O 队伍中编号为 $i$ 的选手的程序设计水平。

第四行包含一个正整数 $Q$，表示比赛场数。

接下来的 $Q$ 行，第 $i$ 行包含两个正整数 $l_i,r_i$，表示第 $i$ 长比赛的参数 $l,r$。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个非负整数，表示第 $i$ 场比赛中所有可能的比赛的精彩程度之和对 $2^{64}$ 取模的结果。

样例一

input

0 2
2 1
1 2
1
1 2

output

8

explanation

当 $p=1,q=2$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $2\times 2=4$。

当 $p=1,q=1$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $1$ 号选手，比赛精彩程度为 $2\times 1=2$。

当 $p=2,q=2$ 的时候，小 N 会派出 $2$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $1\times 2=2$。

样例二

见附加文件中的 ex_match2.in 与 ex_match2.ans。

该样例满足测试点 $1\sim 2$ 的限制。

样例三

见附加文件中的 ex_match3.in 与 ex_match3.ans。

该样例满足测试点 $3\sim 5$ 的限制。

子任务

对于所有数据，保证：$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$ 且 $\{a_i\}$ 和 $\{b_i\}$ 分别构成了从 $1$ 到 $n$ 的排列。

特殊性质 A：保证 $a$ 是均匀随机生成的 $1\sim n$ 的排列。

特殊性质 B：保证 $b$ 是均匀随机生成的 $1\sim n$ 的排列。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$