题目描述

有一个包含 $N^2$ 个顶点的无向图。初始时，图中没有任何边。对于每一组满足 $0 \leq i, j < N$ 的整数对 $(i, j)$，都有一个对应的顶点，记作 $(i, j)$。

给定 $Q$ 个查询。对于第 $i$ 个查询，给出四个整数 $a_i, b_i, c_i, d_i$，请按以下方式依次处理每个查询：

• 对于每个 $k\ (0 \leq k < N)$，在两个顶点 $((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$ 个查询后图的连通分量数。

样例 1

输入

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

输出

6
4
4

样例 2

输入

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

输出

14
11
11

样例 3

输入

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)$
• 所有输入值均为整数

样例解释 1

对于第 $1$ 个查询，会在顶点 $(0, 0)$ 与 $(1, 2)$、$(1, 1)$ 与 $(2, 0)$、$(2, 2)$ 与 $(0, 1)$ 之间分别添加一条边。这样连通分量数会从 $9$ 变为 $6$。

样例解释 2

经过查询处理后，图可能不再是简单图。

由 ChatGPT 4.1 翻译