小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支
�
n 个人的队伍，选手在每支队伍内都是从
1
1 到
�
n 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为
�
i（
1
≤
�
≤
�
1≤i≤n）的选手的程序设计水平为
�
�
a
i
；小 O 率领的队伍中，编号为
�
i（
1
≤
�
≤
�
1≤i≤n）的选手的程序设计水平为
�
�
b
i
。特别地，
{
�
�
}
{a
i
} 和
{
�
�
}
{b
i
} 还分别构成了从
1
1 到
�
n 的排列。
每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数
�
,
�
l,r（
1
≤
�
≤
�
≤
�
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
2
64
取模的结果即可。