题目背景

本题数据已加强。

小 X 忙了一天，于是打起了一款叫斗之魂的游戏。

题目描述

小 X 要击败 $n$ 个 BOSS，他可以选择以下两种击败 BOSS 的方式：

1. 独自一人击败第 $i$ 个 BOSS 并获得 $k_{i,0}$ 块稀有金属，且保证 $k_{i,0}=k_{i,1}=k_{i,2}$。
2. 和小 Y 一起击败第 $i$ 个 BOSS ，小 X 理应获得 $k_{i,1}$ 块稀有金属，小 Y 理应获得 $k_{i,2}$ 块稀有金属，但是 BOSS 本身实力并没有因为人数的改变而改变，击败难度相对要简单一点，所以系统判定两人实际各获得 $k_{i,0}$ 块稀有金属，其中保证 $\dfrac{1}{k_{i,0}}=\dfrac{1}{k_{i,1}}+\dfrac{1}{k_{i,2}}$。

小 X 已经计划好用第 $b_i$ 种方式击败第 $i$ 个 BOSS，但是考虑到某些因素，小 X 有 $q$ 次询问，每次询问给定一个正整数 $m$，为小 X 击败完所有 BOSS 后获得的稀有金属总数，已知 $k_{i,0},k_{i,1},k_{i,2}$ 均为正整数，求每次询问后所有可能的 $k$ 的值的方案数，两种方案不同当且仅当至少存在一个 $k$ 的值不同，由于这个答案可能很大，你只需要输出它对 $998244353$ 取模后的结果。

输入格式

第一行有两个整数 $n$ 和 $q$，分别表示 BOSS 个数和小 X 的询问次数。

第二行有 $n$ 个正整数 $b_i$，表示小 X 用 $b_i$ 种方式击败第 $i$ 个 BOSS。

接下来的 $q$ 行中每行有一个整数 $m$，为该次询问中小 X 击败完所有 BOSS 后获得的稀有金属总数。

输出格式

输出共 $q$ 行，第 $i$ 行输出一个答案为当小 X 击败完所有 BOSS 后获得的稀有金属总数为 $m$ 时，所有可能的 $k$ 的值的方案数并对它取模 $998244353$ 后的结果。

2 2
2 1
3
4

4
7

5 5
1 2 1 2 1
4
6
8
10
12

0
9
119
630
2210

提示

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1 \le n \le 1.5 \times 10^5$，$1 \le m \le 2.5 \times 10^5$，$1 \le b_i \le 2$，$1 \le q \le 10^5$。

样例解释 #1：

• 当 $m=3$ 时，所有可能的 $k$ 的值的方案数为 $4$。

  第 $1$ 种：$k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=2$

  第 $2$ 种：$k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$

  第 $3$ 种：$k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$

  第 $4$ 种：$k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=1$

• 当 $m=4$ 时，所有可能的 $k$ 的值的方案数为 $7$。

  第 $1$ 种：$k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=3$

  第 $2$ 种：$k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=2$

  第 $3$ 种：$k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=2$

  第 $4$ 种：$k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=2$

  第 $5$ 种：$k_{1,0}=3,k_{1,1}=4,k_{1,2}=12,k_{2,0}=k_{2,1}=k_{2,2}=1$

  第 $6$ 种：$k_{1,0}=3,k_{1,1}=6,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$

  第 $7$ 种：$k_{1,0}=3,k_{1,1}=12,k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$