Multiplicative Function Inversion

This is a non-traditional problem.

Given a multiplicative function \(f(d)\), you are provided with some terms of \(g(n)=\sum_{d|n} f(d)\) modulo \(998244353\). In particular, the input includes \(k\) values: \(g(1), g(2), \ldots, g(k)\). Then, there are \(t\) queries. For each query, given an integer \(d\) (with \(1\le d\le k\)), compute \(f(d)\) modulo \(998244353\).

Hint: Using Möbius inversion, note that \[ f(n)=\sum_{d|n}\mu(d)\,g(n/d), \] where \(\mu(d)\) is the Möbius function. Recall that the Möbius function \(\mu(n)\) is defined as follows:

• \(\mu(1)=1\).
• \(\mu(n)=0\) if \(n\) has a squared prime factor.
• \(\mu(n)=(-1)^k\) if \(n\) is the product of \(k\) distinct primes.

inputFormat

The first line contains two integers \(k\) and \(t\), where \(k\) is the number of provided values for \(g(n)\) (for \(n=1\) to \(k\)) and \(t\) is the number of queries.

The second line contains \(k\) space-separated integers representing \(g(1), g(2), \ldots, g(k)\) (all modulo \(998244353\)).

Each of the next \(t\) lines contains one integer \(d\) (with \(1 \le d \le k\)).

outputFormat

For each query, output \(f(d)\) modulo \(998244353\) on a separate line.

sample

4 3
1 3 4 6
1
2
4

1
2
3