题目内容

你有一个长度为 $n$ 的非负整数序列 $A = [A_1, A_2, \dots, A_n]$。对于任意区间 $[l, r]$（$1 \le l \le r \le n$），定义其“能量值”为 $A_l \times A_{l+1} \times \dots \times A_r$，即 $\prod_{i=l}^r A_i$。如果某个区间的能量值严格大于 $10^9$，则将其视为 $0$。现在需要进行 $q$ 次查询，每次查询给定一个整数 $L$，请你计算所有长度恰好为 $L$ 的区间的能量值之和。

输入包含多组测试数据。第一行包含一个整数 $T$（$1 \le T \le 10^3$），表示数据组数。保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$，$q$ 的总和也不超过 $3 \times 10^5$。序列中的每个元素 $A_i$ 满足 $0 \le A_i \le 10^9$，每次查询的 $L$ 满足 $1 \le L \le n$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来依次描述每组数据： 每组数据的第一行包含两个整数 $n$ 和 $q$，分别表示序列长度和查询次数。 第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，表示序列中的元素。 接下来 $q$ 行，每行包含一个整数 $L$，表示一次查询的长度。