8896: NOIP2022 T4：比赛（match）
[Creator : ]
Description
小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 $n$ 个人的队伍，选手在每支队伍内都是从 $1$ 到 $n$ 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 $i$（$1 \leq i \leq n$）的选手的程序设计水平为 $a _ i$；小 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$，则比赛的精彩程度为 $m _ a \times m _ b$。
NOIP 总共有 $Q$ 场比赛，每场比赛的参数 $l, r$ 都已经确定，但是 $p, q$ 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 $p, q$（$l \leq p \leq q \leq r$）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 $2 ^ {64}$ 取模的结果即可。
每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 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$，则比赛的精彩程度为 $m _ a \times m _ b$。
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$。
第二行包含 $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}$ 取模的结果。
Constraints
对于所有数据，保证：$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$ 的排列。
| 测试点 | $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$ 的排列。
Sample 1 Input
0 2
2 1
1 2
1
1 2
Sample 1 Output
8
当 $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$。
当 $p = 1, q = 1$ 的时候，小 N 会派出 $1$ 号选手，小 O 会派出 $1$ 号选手，比赛精彩程度为 $2 \times 1 = 2$。
当 $p = 2, q = 2$ 的时候，小 N 会派出 $2$ 号选手，小 O 会派出 $2$ 号选手，比赛精彩程度为 $1 \times 2 = 2$。
Sample 2 Input
0 30
9 30 25 18 7 3 29 15 12 16 14 26 24 5 1 8 13 28 6 17 2 22 4 23 27 10 11 19 20 21
27 24 11 26 7 3 8 15 25 10 1 4 18 14 20 23 9 22 29 30 13 28 19 17 2 21 6 12 5 16
30
1 30
1 30
6 30
3 26
4 26
6 28
1 24
4 30
7 29
3 24
7 30
3 26
4 26
2 29
4 30
6 21
8 29
11 14
15 19
19 20
7 30
25 30
7 9
19 30
7 26
13 26
5 30
15 24
18 21
23 29
Sample 2 Output
330691
330691
221025
204369
186165
186614
205881
260314
185960
167988
202688
204369
186165
284800
260314
81059
168502
3028
7045
1194
202688
7036
2292
43386
138979
68281
239451
34587
5348
11096