行列式是线性代数中重要的研究对象之一。

对于自然数 $n$，$S_n$ 是所有置换的集合，即从 $\{1, 2, \dots, n\}$ 到 $\{1, 2, \dots, n\}$ 的函数，满足 $n$ 个值 $f(1), f(2), \dots, f(n)$ 各不相同。

对于 $f \in S_n$，$\text{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$ 取模后的结果。

输入格式

第一行包含两个整数 $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$ 行，每行包含一个查询：一个整数 $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