题目描述

整数 $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)$ とする。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$M$ 行出力せよ。$i$ 行目には $S_i$ を出力せよ。

题目大意

给定一个 $n$，初始有 $n!$ 个 $n$ 的排列 $S_1,S_2,\dots,S_{n!}$。给出 $m$ 次询问，每次两个数 $a$ 和 $b$（$1 \leq a < b \leq n$），对于任意一个序列 $S$，如果 $S_a > S_b$，那么交换 $S_a$ 和 $S_b$，操作结束后输出此时已经排好序的序列个数。

本题强制在线，每次输入两个数 $x$, $y$，上一次的答案为 $last$，初始为 $1$。

数据以如下方式生成。

• $c_i\ =\ ((x_i\ + last)\ \bmod\ n)\ +\ 1$。
• $ d_i\ =\ ((y_i\ + last\ \times\ 2)\ \bmod\ n)\ +\ 1$。
• $a_i\ =\ \min(c_i,\ d_i)$。
• $b_i\ =\ \max(c_i,\ d_i)$。

2 1
1 1

2

3 4
0 1
2 1
1 1
0 1

2
4
4
6

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

2
4
4
8
16

提示

制約

• $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$

Sample Explanation 1

はじめ、持っている順列は $(1,\ 2)$ と $(2,\ 1)$ です。 $(a_1,\ b_1)\ =\ (1,\ 2)$ です。$1$ 回目の操作を終了した時点で持っている順列は $(1,\ 2)$ が $2$ 個になります。よって $2$ を出力します。

Sample Explanation 2

$(a_i,\ b_i)$ は順に $(1,\ 2),\ (2,\ 3),\ (1,\ 3),\ (1,\ 2)$ です。

Sample Explanation 3

$(a_i,\ b_i)$ は順に $(1,\ 2),\ (3,\ 4),\ (1,\ 5),\ (2,\ 3),\ (4,\ 5)$ です。