Background

The testdata for this problem has been strengthened.

After a busy day, Little X started playing a game called Soul of Battle.

Problem Description

Little X needs to defeat $n$ BOSSes. For the $i$-th BOSS, he can choose one of the following two ways:

1. Defeat the $i$-th BOSS alone and obtain $k_{i,0}$ pieces of rare metal, and it is guaranteed that $k_{i,0}=k_{i,1}=k_{i,2}$.
2. Defeat the $i$-th BOSS together with Little Y. Little X should obtain $k_{i,1}$ pieces of rare metal, and Little Y should obtain $k_{i,2}$ pieces of rare metal. However, the BOSS’s strength does not change with the number of players, and the fight becomes relatively easier, so the system determines that both players actually obtain $k_{i,0}$ pieces of rare metal. It is guaranteed that $\dfrac{1}{k_{i,0}}=\dfrac{1}{k_{i,1}}+\dfrac{1}{k_{i,2}}$.

Little X has already planned to use method $b_i$ to defeat the $i$-th BOSS. However, due to some factors, Little X has $q$ queries. Each query gives a positive integer $m$, which is the total number of rare metals Little X obtains after defeating all BOSSes. It is known that $k_{i,0},k_{i,1},k_{i,2}$ are all positive integers. For each query, find the number of possible assignments of all $k$ values. Two assignments are considered different if and only if there exists at least one $k$ value that is different. Since the answer may be very large, output it modulo $998244353$.

Input Format

The first line contains two integers $n$ and $q$, representing the number of BOSSes and the number of queries.

The second line contains $n$ positive integers $b_i$, meaning that Little X uses method $b_i$ to defeat the $i$-th BOSS.

Each of the next $q$ lines contains an integer $m$, the total number of rare metals Little X obtains after defeating all BOSSes in this query.

Output Format

Output $q$ lines. The $i$-th line should be the number of possible assignments of all $k$ values when the total rare metals obtained by Little X after defeating all BOSSes is $m$, taken modulo $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

Hint

This problem uses bundled tests.

Constraints

For $100\%$ of the data, it is guaranteed that $1 \le n \le 1.5 \times 10^5$, $1 \le m \le 2.5 \times 10^5$, $1 \le b_i \le 2$, and $1 \le q \le 10^5$.

Sample Explanation #1:

• When $m=3$, the number of possible assignments of all $k$ values is $4$.

  Type $1$: $k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=2$

  Type $2$: $k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$

  Type $3$: $k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$

  Type $4$: $k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=1$

• When $m=4$, the number of possible assignments of all $k$ values is $7$.

  Type $1$: $k_{1,0}=1,k_{1,1}=k_{1,2}=2,k_{2,0}=k_{2,1}=k_{2,2}=3$

  Type $2$: $k_{1,0}=2,k_{1,1}=3,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=2$

  Type $3$: $k_{1,0}=2,k_{1,1}=k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=2$

  Type $4$: $k_{1,0}=2,k_{1,1}=6,k_{1,2}=3,k_{2,0}=k_{2,1}=k_{2,2}=2$

  Type $5$: $k_{1,0}=3,k_{1,1}=4,k_{1,2}=12,k_{2,0}=k_{2,1}=k_{2,2}=1$

  Type $6$: $k_{1,0}=3,k_{1,1}=6,k_{1,2}=6,k_{2,0}=k_{2,1}=k_{2,2}=1$

  Type $7$: $k_{1,0}=3,k_{1,1}=12,k_{1,2}=4,k_{2,0}=k_{2,1}=k_{2,2}=1$

Translated by ChatGPT 5