점프 점프 점프

토끼가 평면의 점 $(0, 0)$에서 출발한다. $k$개의 서로 다른 벡터 $(dx_1, dy_1), (dx_2, dy_2), \ldots, (dx_k, dy_k)$가 주어진다. 매 단계마다 토끼는 이 벡터 중 하나를 같은 확률로 골라 현재 점 $(x, y)$에서 $(x + dx_c, y + dy_c)$로 뛴다. 모든 선택은 서로 독립이다.

$x \geq 1$인 모든 격자점 $(x, x)$에는 함정이 있다. 토끼가 함정에 뛰어들면 그 자리에 갇혀 더 이상 움직일 수 없다.

$1 \leq x \leq n$인 각 $x$에 대해, 토끼가 격자점 $(x, x)$에서 함정에 갇힐 확률을 출력하라.

첫 번째 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \leq n \leq 10^5$, $1 \leq k \leq 16$).

이어지는 $k$개의 줄에는 각각 두 정수 $dx_i$와 $dy_i$가 주어진다 ($0 \leq dx_i, dy_i \leq 3$). 모든 벡터는 서로 다르다.

$n$개의 줄을 출력하라. $x$번째 줄에는 토끼가 격자점 $(x, x)$에서 함정에 갇힐 확률을 출력한다.

확률은 분수 $A / B$로 나타낼 수 있고, $B$는 998244353과 서로소임이 보장된다. $A \cdot B^{-1} \bmod 998244353$을 출력하라.

확률은 차례로 $\frac{1}{2}, \frac{1}{8}, \frac{1}{16}, \frac{5}{128}, \frac{7}{256}$이다.