行列式は線形代数学において重要な対象の一つです。

自然数 $n$ に対して、$S_n$ をすべての置換の集合とします。すなわち、$S_n$ は $\{1, 2, \dots, n\}$ から $\{1, 2, \dots, n\}$ への関数 $f$ であって、$n$ 個の値 $f(1), f(2), \dots, f(n)$ がすべて異なるものの集合です。

$f \in S_n$ に対して、$inv(f)$ を置換 $f$ の転倒数、すなわち $i < j$ かつ $f(i) > f(j)$ となるペア $(i, j)$ の個数とします。

サイズ $N \times N$ の行列 $A$ を考えます。$a_{i,j}$ を第 $i$ 行第 $j$ 列の要素とすると、$A$ の行列式は以下のように定義されます。

$$\det(A) = \sum_{f \in S_n} (-1)^{\text{inv}(f)} \prod_{i=1}^{n} a_{i,f(i)}$$

各要素が整数である $N \times N$ 行列 $A$ が与えられます。以下のクエリを $Q$ 回実行してください。

整数 $x$ が与えられたとき、$A - xI$ の行列式の値を求めてください。ここで、$I$ は $N \times N$ の単位行列です。

値が非常に大きくなる可能性があるため、素数 $998\,244\,353$ で割った余りを出力してください。

入力

最初の行には、2つの整数 $N$ と $Q$ ($1 \le N \le 500, 1 \le Q \le 250\,000$) が含まれます。

続く $N$ 行は行列 $A$ を表します。これらの行のうち $i$ 番目の行には $N$ 個の整数が含まれており、そのうち $j$ 番目の整数は $a_{i,j}$ ($0 \le a_{i,j} < 998\,244\,353$) を表します。

続いて $Q$ 行が続き、各行に1つのクエリである整数 $x$ ($0 \le x < 998\,244\,353$) が含まれます。

出力

各クエリについて、答えを別々の行に出力してください。

入出力例

入力 1

3 6
2 4 5
6 3 8
1 6 3
10 9 5 8 3 1

出力 1

407
470
402
495
260
110