#216. 比赛

比赛

题目描述

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

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

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

输入格式

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

第二行包含 nn 个正整数,第 ii 个正整数为 aia _ i,表示小 N 队伍中编号为 ii 的选手的程序设计水平。

第三行包含 nn 个正整数,第 ii 个正整数为 bib _ i,表示小 O 队伍中编号为 ii 的选手的程序设计水平。

第四行包含一个正整数 QQ,表示比赛场数。

接下来的 QQ 行,第 ii 行包含两个正整数 li,ril _ i, r _ i,表示第 ii 场比赛的参数 l,rl, r

输出格式

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

样例 #1

样例输入 #1

0 2
2 1
1 2
1
1 2

样例输出 #1

8

样例 #2

见选手目录下的 match2.inmatch2.ans

样例 #3

见选手目录下的 match3.inmatch3.ans

提示

【样例 1 解释】

p=1,q=2p = 1, q = 2 的时候,小 N 会派出 11 号选手,小 O 会派出 22 号选手,比赛精彩程度为 2×2=42 \times 2 = 4

p=1,q=1p = 1, q = 1 的时候,小 N 会派出 11 号选手,小 O 会派出 11 号选手,比赛精彩程度为 2×1=22 \times 1 = 2

p=2,q=2p = 2, q = 2 的时候,小 N 会派出 22 号选手,小 O 会派出 22 号选手,比赛精彩程度为 1×2=21 \times 2 = 2

【样例 2】

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

【样例 3】

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

【数据范围】

对于所有数据,保证:1n,Q2.5×1051 \leq n, Q \leq 2.5 \times 10 ^ 51lirin1 \leq l _ i \leq r _ i \leq n1ai,bin1 \leq a _ i, b _ i \leq n{ai}\{a _ i\}{bi}\{b _ i\} 分别构成了从 11nn 的排列。

测试点 nn QQ 特殊性质 A 特殊性质 B
1,21, 2 30\leq 30
3,4,53, 4, 5 3,000\leq 3,000
6,76, 7 105\leq 10 ^ 5 5\leq 5
8,98, 9 2.5×105\leq 2.5 \times 10 ^ 5
10,1110, 11 105\leq 10 ^ 5
12,1312, 13 2.5×105\leq 2.5 \times 10 ^ 5
14,1514, 15 105\leq 10 ^ 5
16,1716, 17 2.5×105\leq 2.5 \times 10 ^ 5
18,1918, 19 105\leq 10 ^ 5
20,2120, 21 2.5×105\leq 2.5 \times 10 ^ 5
22,2322, 23 105\leq 10 ^ 5
24,2524, 25 2.5×105\leq 2.5 \times 10 ^ 5

特殊性质 A:保证 aa 是均匀随机生成的 1n1 \sim n 的排列。

特殊性质 B:保证 bb 是均匀随机生成的 1n1 \sim n 的排列。