Определитель — один из важнейших объектов линейной алгебры.

Для натурального числа $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)$, таких что $i < j$, но $f(i) > f(j)$.

Рассмотрим матрицу $A$ размера $N \times N$. Пусть $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)}$$

Дана матрица $A$ размера $N \times N$, где каждый элемент является целым числом. Необходимо выполнить $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