题目描述

小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP! 小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 $n$ 个人的队伍，选手在每支队伍内都是从$1$ 到 $n$ 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 $i (1 ≤ i ≤ n)$ 的选手的程序设计水平为 $a_i$；小 O 率领的队伍中，编号为 $i (1 ≤ i ≤ n)$的选手的程序设计水平为 $b_i$。特别地，{$a_i$} 和 {$b_i$} 还分别构成了从 $1$ 到 $n$ 的排列。 每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数$l, r (1 ≤ l ≤ r ≤ n)$，表示这一场比赛会邀请两队中编号属于 $[l, r]$ 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 $p, q (l ≤ p ≤ q ≤ r)$，只有编号属于 [p, q] 的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号在 $[p, q]$ 内的、程序设计水平值最大的选手参加比赛。假定小 N 排出的选手水平为 $m_a$，小 O 派出的选手水平为 $m_b$，则比赛的精彩程度为 $m_a$ × $m_b$。 NOIP 总共有 $Q$ 场比赛，每场比赛的参数 $l, r$ 都已经确定，但是 $p, q$ 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 $p, q (l ≤ p ≤ q ≤ 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}$ 取模的结果。

输入样例

0 2
2 1
1 2
1
1 2

输出样例

8

提示

【样例 1 解释】 当 $p = 1, q = 2$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $2 × 2 = 4$。 当 $p = 1, q = 1$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $1$ 号选手，比赛精彩程度为 $2 × 1 = 2$。 当 $p = 2, q = 2$ 的时候，小 N 会派出 $2$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $1 × 2 = 2$。 【子任务】 对于所有数据，保证：$1 ≤ n, Q ≤ 2.5 × 10^5$，$1 ≤ l_i ≤ r_i ≤ n$，$1 ≤ a_i, b_i ≤ n$ 且 {$a_i$}和 {$b_i$} 分别构成了从 $1$ 到 $n$ 的排列。

测试点	n	Q	特殊性质 A	特殊性质 B
1,2	≤ 30	≤ 30	是	是
3,4,5	≤ 3, 000	≤ 3, 000
6,7	≤ 105	≤ 5
8,9	≤ 2.5 × 105
10,11	≤ 105		否	否
12,13	≤ 2.5 × 105
14,15	≤ 105	≤ 105	是	是
16,17	≤ 2.5 × 105	≤ 2.5 × 105
18,19	≤ 105	≤ 105		否
20,21	≤ 2.5 × 105	≤ 2.5 × 105
22,23	≤ 105	≤ 105	否
24,25	≤ 2.5 × 105	≤ 2.5 × 105

特殊性质 A: 保证 $a$ 是均匀随机生成的 $1 ∼ n$ 的排列。 特殊性质 B: 保证 $b$ 是均匀随机生成的 $1 ∼ n$ 的排列。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。