Le déterminant est l'un des objets importants étudiés en algèbre linéaire.

Pour un nombre naturel $n$, $S_n$ est l'ensemble de toutes les permutations : les fonctions de $\{1, 2, \dots, n\}$ vers $\{1, 2, \dots, n\}$ telles que les $n$ valeurs $f(1), f(2), \dots, f(n)$ soient toutes distinctes.

Pour $f \in S_n$, $\text{inv}(f)$ est le nombre d'inversions dans la permutation $f$ : le nombre de paires $(i, j)$ telles que $i < j$ mais $f(i) > f(j)$.

Considérons une matrice $A$ de taille $N \times N$. Soit $a_{i,j}$ l'élément à la ligne $i$ et à la colonne $j$. Le déterminant de $A$ est :

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

Nous avons une matrice $A$ de taille $N \times N$ où chaque élément est un entier. Effectuons $Q$ requêtes de la forme suivante : Lorsqu'un entier $x$ est donné, affichez la valeur du déterminant de $A - xI$, où $I$ est la matrice identité de taille $N \times N$.

Comme la valeur peut être très grande, affichez le résultat modulo le nombre premier $998\,244\,353$.

Entrée

La première ligne contient deux entiers $N$ et $Q$ ($1 \le N \le 500$, $1 \le Q \le 250\,000$).

Les $N$ lignes suivantes décrivent la matrice $A$. La $i$-ième de ces lignes contient $N$ entiers, et le $j$-ième de ces entiers représente $a_{i,j}$ ($0 \le a_{i,j} < 998\,244\,353$).

Ensuite, $Q$ lignes suivent, chacune contenant une requête : un entier $x$ ($0 \le x < 998\,244\,353$).

Sortie

Pour chaque requête, affichez la réponse sur une ligne séparée.

Exemples

Entrée 1

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

Sortie 1

407 470 402 495 260 110