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

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

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

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

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

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

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

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