Wyznacznik jest jednym z ważnych obiektów w algebrze liniowej.

Dla liczby naturalnej $n$, $S_n$ jest zbiorem wszystkich permutacji: funkcji ze zbioru $\{1, 2, \dots, n\}$ w $\{1, 2, \dots, n\}$ takich, że wszystkie $n$ wartości $f(1), f(2), \dots, f(n)$ są różne.

Dla $f \in S_n$, $\text{inv}(f)$ to liczba inwersji w permutacji $f$: liczba par $(i, j)$ takich, że $i < j$, ale $f(i) > f(j)$.

Rozważmy macierz $A$ o rozmiarze $N \times N$. Niech $a_{i,j}$ będzie elementem w $i$-tym wierszu i $j$-tej kolumnie. Wyznacznik macierzy $A$ wynosi:

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

Dana jest macierz $A$ o rozmiarze $N \times N$, w której każdy element jest liczbą całkowitą. Wykonaj $Q$ następujących zapytań.

Dla danej liczby całkowitej $x$, wypisz wartość wyznacznika macierzy $A - xI$, gdzie $I$ jest macierzą jednostkową o rozmiarze $N \times N$.

Ponieważ wartość może być bardzo duża, wypisz wynik modulo liczba pierwsza $998\,244\,353$.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $N$ oraz $Q$ ($1 \le N \le 500$, $1 \le Q \le 250\,000$).

Kolejne $N$ linii opisuje macierz $A$. $i$-ta z tych linii zawiera $N$ liczb całkowitych, a $j$-ta z tych liczb reprezentuje $a_{i,j}$ ($0 \le a_{i,j} < 998\,244\,353$).

Następnie następuje $Q$ linii, z których każda zawiera jedno zapytanie: liczbę całkowitą $x$ ($0 \le x < 998\,244\,353$).

Wyjście

Dla każdego zapytania wypisz wynik w osobnej linii.

Przykład

Wejście 1

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

Wyjście 1

407
470
402
495
260
110