题目描述

$N^2$ 頂点からなる無向グラフがあります。はじめ、グラフは辺を持ちません。 $0\ \leq\ i,\ j\ <\ N$ を満たす整数の組 $(i,\ j)$ それぞれについて、それに対応する頂点がひとつ存在し、その頂点を $(i,\ j)$ と呼びます。

$Q$ 個のクエリが与えられます。$i$ 番目のクエリでは $4$ つの整数 $a_i,\ b_i,\ c_i,\ d_i$ が与えられるので以下のように順番に処理してください。

• 各 $k\ (0\ \leq\ k\ <\ N)$ について、$2$ 頂点 $ ((a_i+k)\ \bmod\ N,\ (b_i+k)\ \bmod\ N),\ ((c_i+k)\ \bmod\ N,\ (d_i+k)\ \bmod\ N) $ 間に辺を追加してください。その後、グラフの連結成分数を出力してください。

输入格式

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

$N$ $Q$ $a_1$ $b_1$ $c_1$ $d_1$ $a_2$ $b_2$ $c_2$ $d_2$ $\vdots$ $a_Q$ $b_Q$ $c_Q$ $d_Q$

输出格式

$Q$ 行出力してください。$i$ 行目には $i$ 番目のクエリにおけるグラフの連結成分数を出力してください。

题目大意

你有一张包含 $n^2$ 个节点的图，每个节点用二元组 $(i,j)$ 表示（$0\le i<n$，$0\le j<n$），初始时没有边。

你需要依次进行 $q$ 次操作，每次操作给定四个参数 $a,b,c,d$，对于每个 $0\le k<n$，你会在节点 $((a+k)\bmod n,(b+k)\bmod n)$ 和 $((c+k)\bmod n,(d+k)\bmod n)$ 之间连一条无向边。

请你计算每次操作后这张图的连通块数量。

3 3
0 0 1 2
2 0 0 0
1 1 2 2

6
4
4

4 3
0 0 2 2
2 3 1 2
1 1 3 3

14
11
11

6 5
0 0 1 1
1 2 3 4
1 1 5 3
2 0 1 5
5 0 3 3

31
27
21
21
19

提示

制約

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $0\ \leq\ a_i,\ b_i,\ c_i,\ d_i\ <\ N$
• $(a_i,\ b_i)\ \neq\ (c_i,\ d_i)$
• 入力される値はすべて整数

Sample Explanation 1

$1$ 番目のクエリでは頂点 $(0,\ 0),\ (1,\ 2)$ 間、$(1,\ 1),\ (2,\ 0)$ 間、$(2,\ 2),\ (0,\ 1)$ 間に辺が追加されます。これにより連結成分数は $9$ から $6$ に変化します。

Sample Explanation 2

クエリ処理の結果、グラフは単純グラフではなくなることがあります。