解题思路

给定原数组 a 和重复次数数组 b，新数组 a' 是把 a_i 连续复制 b_i 次拼接而成。a' 的长度可能非常大（可达 ∑b_i），不能直接构造。 核心做法：前缀和 + 二分定位块。

1. 预处理两条前缀数组

   • 位置前缀（块边界）：prefB[i] = b_1 + b_2 + … + b_i。它表示在新数组 a' 中，第 i 个数所对应的“块”的右端位置。 据此，对任意位置 p，用二分（lower_bound）找到最小的 i 使 prefB[i] ≥ p，即可定位 p 属于的块下标 i。
   • 加权前缀和：prefW[i] = a_1*b_1 + a_2*b_2 + … + a_i*b_i，用于快速求解整块区间的和。

题目内容

你有两个长度为 $n$ 的数组 $a$ 和 $b$ ，数组 $a$ 中每个元素 $a_i$ 复制 $b_i$ 次后,可以得到新数组 $a'$ 。例如，假设 $a=[8,9,7,5,7]，b=[1,2,2,1,3]$ ，则新数组 $a'=[8,9,9,7,7,5,7,7,7]$ 。

你需要回答 $q$ 次询问，其中第 $i$ 次询问会给出两个参数 $l_i$ 和 $r_i$，你需要计算新数组 $a'$ 中下标在 $[l_i,r_i]$ 范围内所有元素的和。

输入描述

输入第一行有一个整数 $n(1≤n≤10^5)$，表示数组的长度。

第二行有 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤n)$ ，表示题目给定的数组 $a$ 。

第三行有 $n$ 个整数 $b_1,b_2,…,b_n(1≤b_i≤n)$ ，表示题目给定的数组 $b$ 。

第四行有一个整数 $q(1≤q≤10^5)$ ，表示询问的次数。

接下来 $q$ 行中第 $i$ 行有两个正整数 $l_i$ 和 $r_i(1≤l_i,r_i≤\sum^n_{i=1}b_i)$ ，表示第 $i$ 次询问中的下标范围。

输出描述

对于每一个询问，输出一行一个整数，表示新数组 $a'$ 下标范围内所有元素的和。

样例1

输入

5
8 9 7 5 7
1 2 2 1 3
2
3 7
1 9

输出

35
66

说明

新数组 $a'=[8,9,9,7,7,5,7,7,7]$ ，对于第一个询问，答案为 $9+7+7+5+7=35$ ；对于第二个询问，实际上问的是新数组的和，答案为 $8+9+35+7+7=66$ 。