問題文

整数 $N$ と $M$ 個の整数の組 $(a_1, b_1), (a_2, b_2), \\dots, (a_M, b_M)$ があります。各 $a_i, b_i$ は $1 \\leq a_i \\lt b_i \\leq N$ を満たします。

はじめ、あなたは $(1,2,\\dots,N)$ の順列を $N!$ 種類すべて持っています。
あなたは $M$ 回の操作を行います。$i$ 回目の操作は次の通りです。

• 持っている $N!$ 個の順列すべてに対して次の処理を行う。
  • 順列の $a_i$ 番目の要素と $b_i$ 番目の要素の値を比較して、前者の方が大きければ両者を swap する。

$1 \\leq i \\leq M$ について、$i$ 回目の操作を終了した時点で持っている順列のうち昇順にソートされている列の個数を $S_i$ とします。
$S_1, S_2, \\dots, S_M$ を出力してください。

ただし、入力では $(a_i, b_i)$ の代わりに整数の組 $(x_i, y_i)$ が与えられます。
$(a_i, b_i)$ の値は $x_i, y_i, S_{i-1}$ を用いて次の手順で得ることができます。(便宜上 $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 \\lt 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$ 回目の操作を終了した時点で持っている順列は $(1, 2)$ が $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)$ です。