Định thức là một trong những đối tượng quan trọng trong đại số tuyến tính.

Với một số tự nhiên $n$, $S_n$ là tập hợp tất cả các hoán vị: các hàm từ $\{1, 2, \dots, n\}$ đến $\{1, 2, \dots, n\}$ sao cho tất cả $n$ giá trị $f(1), f(2), \dots, f(n)$ đều khác nhau.

Với $f \in S_n$, $inv(f)$ là số lượng nghịch thế trong hoán vị $f$: số lượng các cặp $(i, j)$ sao cho $i < j$ nhưng $f(i) > f(j)$.

Xét ma trận $A$ kích thước $N \times N$. Gọi $a_{i,j}$ là phần tử ở hàng $i$ và cột $j$. Định thức của $A$ là:

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

Chúng ta có một ma trận $A$ kích thước $N \times N$ với mỗi phần tử là một số nguyên. Hãy thực hiện $Q$ truy vấn sau đây.

Khi cho trước số nguyên $x$, hãy in ra giá trị định thức của $A - xI$, trong đó $I$ là ma trận đơn vị kích thước $N \times N$.

Vì giá trị có thể rất lớn, hãy in ra kết quả theo modulo số nguyên tố $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ ($1 \le N \le 500$, $1 \le Q \le 250\,000$).

$N$ dòng tiếp theo mô tả ma trận $A$. Dòng thứ $i$ trong số đó chứa $N$ số nguyên, và số nguyên thứ $j$ đại diện cho $a_{i,j}$ ($0 \le a_{i,j} < 998\,244\,353$).

Sau đó là $Q$ dòng, mỗi dòng chứa một truy vấn: một số nguyên $x$ ($0 \le x < 998\,244\,353$).

Dữ liệu ra

Với mỗi truy vấn, in ra kết quả trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

407
470
402
495
260
110