행렬식(determinant)은 선형대수학에서 다루는 중요한 대상 중 하나입니다.

자연수 $n$에 대하여, $S_n$은 $\{1, 2, \dots, n\}$에서 $\{1, 2, \dots, n\}$으로 가는 함수 중 $n$개의 값 $f(1), f(2), \dots, f(n)$이 모두 다른 모든 치환(permutation)의 집합입니다.

$f \in S_n$에 대하여, $\text{inv}(f)$는 치환 $f$의 반전(inversion) 수, 즉 $i < j$이지만 $f(i) > f(j)$인 쌍 $(i, j)$의 개수입니다.

$N \times N$ 크기의 행렬 $A$를 고려합시다. $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)}$$

각 원소가 정수인 $N \times N$ 행렬 $A$가 주어집니다. 다음 질의를 $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