4836 - NOIP2022提高:第四题比赛

通过次数

提交次数

旧版界面

Time Limit : 1 秒

Memory Limit : 512 MB

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

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

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

Input

第一行包含两个正整数 $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$。

Output

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

Examples

Input

Output

Input

2 30
10 17 6 8 11 25 3 12 18 27 19 24 4 2 22 15 26 21 13 29 1 28 5 9 7 20 23 30 16 14
2 22 19 20 5 14 1 25 30 24 27 18 21 4 23 15 8 12 13 29 9 28 6 10 3 16 17 11 26 7
30
1 30
3 24
2 28
2 27
4 25
5 27
4 28
4 30
7 28
7 28
1 30
8 30
8 29
1 27
1 25
9 28
4 27
13 25
7 30
1 4
1 6
2 23
15 28
6 13
5 26
4 22
1 29
21 25
3 15
6 25

Output

Hint

提示

【样例 1 解释】

当 $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$ 。

【样例 2】

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

【样例 3】

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

【数据范围】

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

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

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

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