#R2024A0804. 背包

背包

背包

时间限制:3s3s

空间限制:256MB256MB

题目描述

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

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

数据格式

输入

1122个整数,表示物品数量 nn与询问数量mm

22nn个整数,表示序列vv

33nn个整数,表示序列cc

接下来mm行,每行一个整数表示背包容量VV

输出

输出 mm 行,给出恰好装满背包的方案数。

样例

输入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

数据范围及约定

1n10,1m,v[i],c[i],V1051≤n≤10,1≤m,v[i],c[i],V≤10^5