该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背包

时间限制：$3s$

空间限制：$256MB$

题目描述

有一组物品$1-n$，每个物品有体积$v[i]$，如果选择该物品，必须选择$c[i]$的倍数个。

给定$m$个询问，每次询问包含一个背包的容量$V$，你需要给出恰好装满背包的方案数(对998244353取模)。

数据格式

输入

第$1$行$2$个整数，表示物品数量 $n$与询问数量$m$。

第 $2$ 行$n$个整数，表示序列$v$。

第 $3$ 行$n$个整数，表示序列$c$。

接下来$m$行，每行一个整数表示背包容量$V$。

输出

输出 $m$ 行，给出恰好装满背包的方案数。

样例

输入1

3 4
10 100 1000
1 1 1
1
10
100
1000

输出1

0
1
2
12

输入2

4 10
1 10 100 1000
1 2 3 4
1234
5678
9101
1121
3141
5161
7181
9202
1222
3242

输出2

160
3110
9608
138
913
2513
5435
9874
160
968

数据范围及约定

$1≤n≤10,1≤m,v[i],c[i],V≤10^5$。