该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

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

Input

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

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

第二行包含 $n$ 个正整数 $a_0,a_1,\dots,a_{n-1}$ ($1\leq a_i\leq 10^9$)。

第三行包含 $n$ 个正整数 $b_0,b_1,\dots,b_{n-1}$ ($1\leq b_i\leq 10^9$)。

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

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

Output

对于每组数据输出 $q$ 行，其中第 $i$ 行输出一个整数，即在第 $i$ 次操作完毕之后 $\sum_{i=0}^{n-1} 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