El determinante es uno de los objetos importantes tratados en el álgebra lineal.

Para un número natural $n$, $S_n$ es el conjunto de todas las permutaciones: funciones de $\{1, 2, \dots, n\}$ a $\{1, 2, \dots, n\}$ tales que los $n$ valores $f(1), f(2), \dots, f(n)$ son todos diferentes.

Para $f \in S_n$, $\text{inv}(f)$ es el número de inversiones en la permutación $f$: el número de pares $(i, j)$ tales que $i < j$ pero $f(i) > f(j)$.

Consideremos una matriz $A$ de tamaño $N \times N$. Sea $a_{i,j}$ el elemento en la fila $i$ y columna $j$. El determinante de $A$ es:

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

Tenemos una matriz $A$ de $N \times N$ donde cada elemento es un entero. Realicemos $Q$ consultas de la siguiente forma: Dado un entero $x$, imprima el valor del determinante de $A - xI$, donde $I$ es una matriz identidad de $N \times N$.

Dado que el valor puede ser demasiado grande, imprima la respuesta módulo el número primo $998\,244\,353$.

Entrada

La primera línea contiene dos enteros $N$ y $Q$ ($1 \le N \le 500$, $1 \le Q \le 250\,000$).

Las siguientes $N$ líneas describen la matriz $A$. La $i$-ésima de estas líneas contiene $N$ enteros, y el $j$-ésimo de estos enteros representa $a_{i,j}$ ($0 \le a_{i,j} < 998\,244\,353$).

Luego siguen $Q$ líneas, cada una conteniendo una consulta: un entero $x$ ($0 \le x < 998\,244\,353$).

Salida

Para cada consulta, imprima la respuesta en una línea separada.

Ejemplos

Entrada 1

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

Salida 1

407 470 402 495 260 110