题目描述

给定两个长度为 $n$ 的序列 $a_0,a_1,…,a_{n−1}$ 和 $b_0,b_1,…,b_{n−1}$，你需要依次执行 $q$ 次操作，每次操作将会给出一个整数 $k$ ($0≤k<n$)，对于每个 $i$ ($0≤i<n$)，你需要将 $a_i$ 更新为 $\max(a_i,b(i+k)\ \text{mod}\ n)$。为了证明你确实维护了 $a$ 序列，请在每次操作之后输出 $∑\limits ^{n−1}_{i=0}a_i$ 的值。

输入格式

第一行包含一个正整数 $T$ ($1≤T≤2$)，表示测试数据的组数。

每组数据第一行包含两个正整数 $n,q$ ($1≤n,q≤250000$)，分别表示序列的长度以及操作的次数。

第二行包含 $n$ 个正整数 $a_0,a_1,…,a_{n−1}$ ($1≤a_i≤10^9$)。

第三行包含 $n$ 个正整数 $b_0,b_1,…,b_{n−1}$ ($1≤b_i≤10^9$)。

接下来 $q$ 行，每行一个整数 $k$ ($0≤k<n$)，依次描述每次操作。

输入数据保证每个 $a_i,b_i$ 都是在 $[1,10^9]$ 均匀随机生成得到（样例除外），且每个 $k$ 都是在 $[0,n)$ 均匀随机生成得到（样例除外）。

输出格式

对于每组数据输出 $q$ 行，其中第 $i$ 行输出一个整数，即在第 $i$ 次操作完毕之后 $∑\limits ^{n−1}_{i=0}a_i$ 的值。

输入样例

1
5 5
1 5 3 6 8
2 5 4 7 3
3
2
4
1
0

输出样例

29
31
33
35
36