AT_abc384_g [ABC384G] Abs Sum

题目描述

给定长度为 $N$ 的整数序列 $A,B$ 和长度为 $K$ 的正整数序列 $X,Y$，对于 $k=1,2,3,...,K$，求 $\sum_{i = 1}^{X_k} \sum_{j = 1}^{Y_k} |A_i-B_j|$。

输入格式

第一行输入一个整数 $N$。
第二行输入 $N$ 个整数 $A_1,A_2,A_3,...,A_N$。
第三行输入 $N$ 个整数 $B_1,B_2,B_3,...,B_N$。
第四行输入一个整数 $K$。
接下来共 $K$ 行，每行两个整数，第 $i$ 行输入的数为 $X_i,Y_i$。

输出格式

输出共 $K$ 行，每行一个整数，第 $i$ 行表示当 $k=i$ 时的结果。

输入输出样例 #1

输入 #1

2
2 4
3 5
4
1 1
1 2
2 1
2 2

输出 #1

1
4
2
6

输入输出样例 #2

输入 #2

5
1163686 28892 1263085 2347878 520306
1332157 1202905 2437161 1291976 563395
5
5 3
1 5
2 3
1 2
5 5

输出 #2

13331322
2209746
6366712
207690
20241215

说明/提示

样例解释

测试数据1

当 $k=1$ 时，答案为 $|A_1-B_1|=1$，因此第 $1$ 行输出一个整数 $1$。
当 $k=2$ 时，答案为 $|A_1-B_1|+|A_1-B_2|=1+3=4$，因此第 $2$ 行输出一个整数 $4$。
当 $k=3$ 时，答案为 $|A_1-B_1|+|A_2-B_1|=1+1=2$，因此第 $3$ 行输出一个整数 $2$。
当 $k=4$ 时，答案为 $|A_1-B_1|+|A_1-B_2|+|A_2-B_1|+|A_2-B_2|=1+3+1+1=6$，因此第 $4$ 行输出一个整数 $6$。

数据范围

• $1 \leq N \leq 10^5$
• $0 \leq A_i,B_j \leq 2 \times 10^8$
• $1 \leq K \leq 10^4$
• $1 \leq X_k,Y_k \leq N$