Jump Jump Jump

The rabbit starts at point $(0, 0)$ on the plane. There are $k$ distinct vectors $(dx_1, dy_1), (dx_2, dy_2), \ldots, (dx_k, dy_k)$. On each step, the rabbit chooses one vector $(dx_c, dy_c)$ with equal probability and jumps from its current point $(x, y)$ to $(x + dx_c, y + dy_c)$. All choices are independent.

There are traps at all lattice points $(x, x)$ for $x \geq 1$. Once the rabbit jumps into a trap, it is trapped and cannot move anymore.

For each $x$ such that $1 \leq x \leq n$, output the probability that the rabbit gets trapped at the lattice point $(x, x)$.

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $1 \leq k \leq 16$).

Each of the following $k$ lines contains two integers $dx_i$ and $dy_i$ ($0 \leq dx_i, dy_i \leq 3$). All the vectors are distinct.

Print $n$ lines. On line $x$, print the probability that the rabbit is trapped at the lattice point $(x, x)$.

It is guaranteed that the probability can be written as a fraction $A / B$ where $B$ is coprime to 998244353. Print $A \cdot B^{-1} \bmod 998244353$.

The probabilities are $\frac{1}{2}, \frac{1}{8}, \frac{1}{16}, \frac{5}{128}$, and $\frac{7}{256}$.