题目描述

给定整数 $N, Q$，以及长度为 $Q$ 的整数列 $A=(A\_1, A\_2, \ldots, A\_Q), B=(B\_1, B\_2, \ldots, B\_Q)$。

对于 $k=1,2,\ldots,Q$，请你解决以下问题：

有一个无向图，包含 $N$ 个顶点，顶点编号为 $0$ 到 $N-1$，共有 $N$ 条边。第 $i$ 条边（$0 \leq i < N$）连接顶点 $i$ 和顶点 $(A_k \times i + B_k) \bmod N$。请你求出该无向图的连通分量数。

输入格式

输入以如下格式从标准输入给出。

$N$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出 $k=i$ 时的答案。

样例 1

输入

6 3
2 1
0 1
1 0

输出

2
1
6

样例 2

输入

11 3
9 1
5 3
8 0

输出

3
3
2

样例 3

输入

182 3
61 2
77 88
180 55

输出

36
14
9

说明/提示

限制条件

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 10^5$
• $0 \leq A_k < N$
• $0 \leq B_k < N$
• 所有输入均为整数

样例解释 1

对于 $k=1$，可以分为以下 $2$ 个连通分量：

• 包含顶点 $0,1,3,4$ 的连通分量。
• 包含顶点 $2,5$ 的连通分量。 因此，$k=1$ 时的答案为 $2$。

样例解释 2

对于 $k=1$，可以分为以下 $3$ 个连通分量：

• 包含顶点 $0,1,3,6,10$ 的连通分量。
• 包含顶点 $2,5,7,8,9$ 的连通分量。
• 包含顶点 $4$ 的连通分量。 因此，$k=1$ 时的答案为 $3$。

由 ChatGPT 4.1 翻译