题目描述

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

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

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

输入格式

第一行包含两个正整数 T, n，分别表示测试点编号和参赛人数。如果数据为样例则保证 T = 0。
第二行包含 n 个正整数，第 i 个正整数为 ai，表示小 N 队伍中编号为 i 的选手的程序设计水平。
第三行包含 n 个正整数，第 i 个正整数为 bi，表示小 O 队伍中编号为 i 的选手的程序设计水平。
第四行包含一个正整数 Q，表示比赛场数。接下来的 Q 行，第 i 行包含两个正整数 li, ri，表示第 i 场比赛的参数 l, r。

输出格式

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

样例1数据(其他数据详见附件）

input

0 2
2 1
1 2
1
1 2

output

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 ≤ li ≤ ri ≤ n，1 ≤ ai, bi ≤ n 且 {ai}和 {bi} 分别构成了从 1 到 n 的排列。

附件

match.zip