题解

题面描述

给定一个由$n$个整数组成的数组$\{a_1,a_2,\dots,a_n\}$。小苯对数组中各个区间的乘积很感兴趣，并提出了$q$个询问：对于每个询问给定一个长度$len$，要求计算数组中所有长度为$len$的区间的乘积之和，定义区间$(l,r)$的乘积为 $f(l,r)$=$a_l\times a_{l+1}\times\cdots\times a_r$ 但有个特殊要求：如果某个区间的乘积$f(l,r)>10^9$，则直接将其视为$0$（不计入总和）。

题目内容

小苯有一个由$n$个整数组成的数组{$a_1,a_2,..,a_n$}，他对数组的乘积非常感兴趣，因此他提出了$q$次询问，具体地，每次询问:

• 小苯会询问一个数字$len$，他想知道数组中所有长度为$len$的区间的乘积之和(形式化的:定义$f(l,r)= a_l×a_{l+1}×$$...×a_r$，则对于所有$1≤l≤r≤n$,$r-l+1=len$的$(l,r)$，求 $f(l,r)$ 之和。)

但特别的，懒惰的小苯不希望处理太大的乘积，因此如果某个$f(l,r) > 10^9$，则小苯会直接舍弃此值，即将其视为$0$

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦10^3)$ 代表数据组数，每组测试数据描述如下:

第一行输入两个正整数$n,q(1≦n,q≦3×10^5)$，分别表示数组$a$的长度和小苯的询问次数。

第二行输入$n$个整数$a_1,a_2,… , a_n (0 ≦a≦10^9)$，表示小苯拥有的$a$数组。

接下来$q$行，每行一个整数$len (1 ≦ len ≦n)$，表示当前次的询问。

除此之外，保证单个测试文件的$n$之和不超过$3×10^5$，$q$之和不超过$3×10^5$。

输出描述

对于每组测试数据，输出$q$行，每行一个整数，表示对应询问的答案。

样例1

输入

1
5 2 
1 2 2 1 2
1 
3

输出

8
12

说明

对于第一组测试数据的第一次询问，长度为$1$的区间有$5$个，乘积之和为 $f(1,1)+f(2,2)+f(3,3)+f(4,4)+f(5,5)$$=1+2+2+1+2=8$

对于第一组测试数据的第二次询问，长度为$3$的区间有$3$个，乘积之和为 $f(1,3)+f(2,4)+f(3,5)$$=1×2×2+2×1×2+2×2×1=12$