题目描述

给定整数 $N$ 和 $M$，以及 $M$ 对整数：$(a_1, b_1), (a_2, b_2), \dots, (a_M, b_M)$。每对 $(a_i, b_i)$ 满足 $1 \leq a_i < b_i \leq N$。

初始时，有 $N!$ 种排列 $(1,2,\dots,N)$。
你将进行 $M$ 个操作，第 $i$ 个操作如下。

• 对于你的每一种排列，执行以下步骤：
  • 比较第 $a_i$ 个和第 $b_i$ 个元素。如果前者较大，则交换这两个元素。

对于每个 $1 \leq i \leq M$，令 $S_i$ 表示第 $i$ 个操作结束后，按升序排列的你的排列数。
输出 $S_1, S_2, \dots, S_M$。

输入中给出的是整数对 $(x_i, y_i)$，而不是 $(a_i, b_i)$。
可以根据 $x_i$、$y_i$ 和 $S_{i-1}$ 计算出 $(a_i, b_i)$ 的值。 （为了方便，取 $S_0 = 1$。）

• 令 $c_i = ((x_i + S_{i-1}) \bmod N) + 1$。
• 令 $d_i = ((y_i + S_{i-1} \times 2) \bmod N) + 1$。（这里保证 $c_i \neq d_i$。）
• 令 $a_i = \min(c_i, d_i)$。
• 令 $b_i = \max(c_i, d_i)$。

约束条件

• $2 \leq N \leq 15$
• $1 \leq M \leq 5 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $0 \leq x_i, y_i \leq N - 1$

输入

从标准输入读入数据，数据格式如下：

$N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_M$ $y_M$

输出

输出 $M$ 行，第 $i$ 行应包含 $S_i$。

示例输入 1

2 1
1 1

示例输出 1

2

初始时有排列 $(1, 2)$ 和 $(2, 1)$。
我们有 $(a_1, b_1) = (1, 2)$。在第一个操作结束时，你有两个 $(1, 2)$ 的副本，所以应打印 $2$。

示例输入 2

3 4
0 1
2 1
1 1
0 1

示例输出 2

2
4
4
6

按顺序，$(a_i, b_i)$ 为 $(1, 2), (2, 3), (1, 3), (1, 2)$。

示例输入 3

5 5
4 4
0 4
1 1
2 4
1 2

示例输出 3

2
4
4
8
16

按顺序，$(a_i, b_i)$ 为 $(1, 2), (3, 4), (1, 5), (2, 3), (4, 5)$。