A37631.线性探查法

给定一个大小为 $N$ 的哈希表，并定义以下哈希函数：

$$H(X) = X \mathbin{\mathrm{mod}} N$$

这里，$X \mathbin{\mathrm{mod}} N$ 表示 $X$ 除以 $N$ 后的余数。

接下来给出 $Q$ 个查询，对于每个查询 $i$，若 $X_i$ 已在哈希表中，请你输出其在哈希表中的位置；否则将其插入哈希表，再输出其插入的位置。

我们使用线性探查法解决哈希冲突，即对于要插入的元素 $X$，若 $H(X)$ 已经存在其他元素，则依次检查 $H(X + 1), H(X + 2), H(X + 3), \cdots$ 直至找到内容为空的单元。

$\large{数据范围}$

• $1 \le Q \le N \le 10^5$
• $1 \le X_i \le 10^{12}$

对于每个测试文件，格式如下：

$\tt{N\ Q}$
$\tt{X_1}$
$\tt{X_2}$
$\tt{\vdots}$
$\tt{X_Q}$

对于每个查询 $i$，若 $X_i$ 已在哈希表中，输出其位置，否则将其插入到哈希表，并输出插入的位置。

$\bf{样例\ 1：}$

$X_1 = 13$，$H(13) = 13 \mathbin{\mathrm{mod}} 5 = 3$，所以将 $13$ 插入表中位置 $3$ 处；此时表中元素：

0	1	2	3	4
			13

$X_2 = 28$，$H(28) = 28 \mathbin{\mathrm{mod}} 5 = 3$，但是 $3$ 处已有元素 $13$，所以继续尝试 $H(29) = 29 \mathbin{\mathrm{mod}} 5 = 4$，将 $28$ 插入表中位置 $4$ 处；此时表中元素：

0	1	2	3	4
			13	28

$X_3 = 52$，$H(52) = 52 \mathbin{\mathrm{mod}} 5 = 2$，将 $52$ 插入表中位置 $2$ 处；此时表中元素：

0	1	2	3	4
		52	13	28

$X_4 = 2$，$H(2) = 2 \mathbin{\mathrm{mod}} 5 = 2$，但是 $2$ 处已有元素 $52$，继续尝试 $H(2 + 1) = 3, H(2 + 2) = 4, H(2 + 3) = 0$，将 $2$ 插入表中位置 $0$ 处；此时表中元素：

0	1	2	3	4
2		52	13	28

$X_5 = 100$，$H(100) = 100 \mathbin{\mathrm{mod}} 5 = 0$，但是 $0$ 处已有元素 $52$，继续尝试 $H(100 + 1) = 1$，将 $100$ 插入表中位置 $1$ 处；此时表中元素：

0	1	2	3	4
2	100	52	13	28