题目描述

现有一个整数$n$,和一个初始点值均为 $0$ 的无限长的数轴。

给定一个序列 ${p_1},{p_2},{p_3},……,{p_n}$ ，表示有$n$个数轴上的点。

再给出一个序列用于修改$n$个点的值， ${a_{p_1}},{a_{p_2}},{a_{p_3}},……,{a_{p_n}}$ ，分别表示数轴上 ${p_i}$ 点的值。

• 定义 $S(x)=\sum_{i=-\infty}^{x} {a_i}$。

随后给出 $q$ 个查询，每个查询：

• 给出两个整数 $l,r$ ，求$S(r)-S(l)$的答案。

输入格式

输入一个整数$T(1 \leq T \leq 10^5)$,表示测试样例组数。

对于每组测试样例：

第一行一个整数$n(1 \leq n \leq 2\times 10^5 )$，表示序列长度。

第二行$n$个整数，${p_1},{p_2},{p_3},……,{p_n}$，表示有$n$个数轴上的点，$( |{p_i}| \leq 10^9 )$且各不相同。

第三行$n$个整数，${a_{p_1}},{a_{p_2}},{a_{p_3}},……,{a_{p_n}}$，分别表示数轴上 ${p_i}$ 点的值，$( |{a_{p_i}}| \leq 10^9 )$。

第四行一个整数$q(1 \leq q \leq 2\times 10^5 )$, 表示查询次数。

随后$q$行，每行输入两个整数$l,r（|l|,|r| \leq 10^9）$。

多组数据范围保证，$\sum n,\sum q \leq 2\times 10^5$

输出格式

每组测试样例输出$q$行。

每行输出一个对 $10^9+7$ 取模的整数$ans$，代表查询答案。

输入输出样例 #1

输入 #1

1
4
-10 0 10 20
-5 15 -3 10
4
-20 -10
-5 15
20 -20
-100 -50

输出 #1

1000000002
12
999999990
0