Problem Description

There is a sequence $\{a_n\}$ such that for all $n > m$, $a_n=\sum\limits_{j=1}^m a_{n-j}$. Also, $a_1,a_2,\cdots,a_m$ are positive integers given in the input.

There are $q$ queries. Each query gives a positive integer $x$, and asks how many distinct positive-integer sets $S$ (no repeated elements) satisfy $\sum\limits_{s\in S}a_s=x$. The answer is taken modulo the prime $998244353$.

This problem contains multiple test cases.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases. For each test case:

The first line contains two integers $m,q$.

The second line contains $m$ integers $a_1,a_2,\cdots,a_m$.

The third line contains $q$ integers, where each integer represents one query.

Output Format

For each query, output one line containing the answer.

2
2 5
1 1
3 5 7 9 11
3 5
1 2 5
4 7 10 18 22

3
3
3
5
5
0
1
1
1
1

Hint

For all testdata, $T=5$, $2 \le m \le 100$, $1 \le q,a_i \le 100$, $1 \le x \le 10^{18}$.

$$\def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c}\hline \textbf{测试点编号}&\bm{m\le}&\bm{q \le }&\bm{a_i \le }& \bm{x \le}&\bm{\textbf{特殊性质}}\cr\hline \textsf1\sim \sf2 & 8&8 & 8 & 100\cr\hline \sf3\sim 5 & 15& &15&10^3 \cr\hline \textsf6 & & & & 1 &\cr\hline \sf7\sim 11 & & 1& & & \textsf{A}\cr\hline \sf12\sim 16 & 2& & &\cr\hline \sf17\sim 20 & &\cr\hline \end{array}$$

$\textsf A$: $m=10$, and $x$ is generated uniformly at random among all possible $x$.

Translated by ChatGPT 5