题目描述

从妹妹丝碧卡还在娘胎里的时候,利格鲁就已经是一个妹控了。

为了有更强大的力量保护妹妹以及在妹妹面前无所不能的哥哥形象,他坚持锻炼,想要成为一个能够独当一面的强者。锻炼先从练力气开始,于是他开始了搬砖。

利格鲁在路上画了一排若干个(可以认为是无限个)格子,每个格子按顺序有个编号,编号从$0$开始。一开始$0$到$n-1$的格子上都叠着$a_i$块砖。他会从$0$号格子开始搬砖。当他在第$i$个格子时,设当前所在的格子有$x$块砖,他会将这$x$块转拿走分别放到编号在$[max(n,i+1),i+x]$的格子上,每个格子各一块砖(多余的砖丢掉)。接下来他会走到第$i+1$的格子上,继续进行这样的锻炼。

树荫下,刚出生不久的丝碧卡在蕾姆怀中睁大眼睛看着辛勤锻炼着的利格鲁。你坐在旁边悄悄对蕾姆说:“我知道他走到第$x$个格子的时候,第$x$个格子上有多少块砖。”

蕾姆半醒半疑地歪了歪头,过了一会儿,等到利格鲁快到了第$x$个格子前,她发现这真的被你说中了。

于是第二天,利格鲁看到了$T$排的砖......

他额头上长长的角瞬间挺了出来,怒喝一声:“为了丝碧卡!”然后卖力地干活去了。

补充一下,这$T$排的砖互不干扰。它们的$n$也不一样。特别地,由于聪明的蕾姆似乎发现了什么秘密,所以特意地将一开始每一个格子上的砖数设成了${n-1,n,n+1}$中的数。还是树荫下,蕾姆抱着丝碧卡,向你提出若干个询问。

输入格式

第一行一个正整数$T$。

接下来$T$组,每组输入格式如下:

第一行输入整数$n,q$。$q$表示询问个数。

第二行$n$个整数表示$a_{0...n-1}$。

第三行$q$个整数$x_{1...q}$表示询问。

输出格式

对于每组数据分别输出一行$q$个数,表示各个询问的答案。

输入样例1

5
6 3
7 6 6 7 7 5
7 8 10
4 5
4 4 4 3
4 5 6 7 10
6 3
6 5 7 6 6 6
6 9 10
4 6
3 4 3 3
14 19 15 4 9 16
5 6
4 4 4 5 4
28 59 55 46 99 34

输出样例1

7 6 7
4 4 4 3 4
6 7 6
3 3 3 3 4 3
5 4 4 4 4 4

样例解释1

对于第一个数据,一开始各个位置上的砖数为$7,6,6,7,7,5$。

到位置$0$的时候,砖数为$7,6,6,7,7,5$。

到位置$1$的时候,砖数为$0,6,6,7,7,5,1,1$。

到位置$2$的时候,砖数为$0,0,6,7,7,5,2,2$。

到位置$3$的时候,砖数为$0,0,0,7,7,5,3,3,1$。

到位置$4$的时候,砖数为$0,0,0,0,7,5,4,4,2,1,1$。

到位置$5$的时候,砖数为$0,0,0,0,0,5,5,5,3,2,2,1$。

到位置$6$的时候,砖数为$0,0,0,0,0,0,6,6,4,3,3,1$。

到位置$7$的时候,砖数为$0,0,0,0,0,0,0,7,5,4,4,2,1$,此时询问$7$答案为$7$。

到位置$8$的时候,砖数为$0,0,0,0,0,0,0,0,6,5,5,3,2,1,1$,此时询问$8$答案为$6$。

到位置$9$的时候,砖数为$0,0,0,0,0,0,0,0,0,6,6,4,3,2,2$。

到位置$10$的时候,砖数为$0,0,0,0,0,0,0,0,0,0,7,5,4,3,3,1$,此时询问$10$答案为$7$。

数据范围

本题采取捆绑测试。

对于所有的数据,$T\leq10,q\leq10^5,x_i \geq n$