题目描述

有一个无向图，有 $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) \mod N, (b_i+k) \mod N)$ 和 $((c_i+k) \mod N, (d_i+k) \mod N)$ 之间添加一条边。然后，打印图中当前连接组件的数量。

约束条件

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

输入

输入以标准格式给出，格式如下：

$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

示例输出 1

6
4
4

第一个查询在 $(0,0), (1,2)$、$(1,1), (2,0)$ 和 $(2,2), (0,1)$ 之间添加了边，使得连接组件的数量从 9 变为 6。

示例输入 2

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

示例输出 2

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

示例输出 3

31
27
21
21
19