兔子从平面上的点 $(0, 0)$ 出发。给定 $k$ 个不同的向量 $(dx_1, dy_1), (dx_2, dy_2), \dots, (dx_k, dy_k)$。在每一步中，兔子会以相同的概率随机选择一个向量 $(dx_c, dy_c)$，然后从当前点 $(x, y)$ 跳跃到 $(x + dx_c, y + dy_c)$。所有的选择都是相互独立的。

对于所有 $x \ge 1$，格点 $(x, x)$ 处设有陷阱。一旦兔子跳入陷阱，它就会被困住，无法再移动。

对于每个满足 $1 \le x \le n$ 的 $x$，输出兔子被困在格点 $(x, x)$ 的概率。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^5, 1 \le k \le 16$)。

接下来的 $k$ 行，每行包含两个整数 $dx_i$ 和 $dy_i$ ($0 \le dx_i, dy_i \le 3$)。所有向量均不相同。

输出格式

输出 $n$ 行。在第 $x$ 行，输出兔子被困在格点 $(x, x)$ 的概率。保证该概率可以表示为分数 $A/B$，其中 $B$ 与 $998\,244\,353$ 互质，因此请输出 $A \cdot B^{-1} \pmod{998\,244\,353}$。

样例

输入 1

5 3
0 0
0 1
1 0

输出 1

499122177
873463809
935854081
959250433
970948609

说明

概率分别为 $\frac{1}{2}, \frac{1}{8}, \frac{1}{16}, \frac{5}{128}$ 和 $\frac{7}{256}$。