绘世之卷

Problem Description

「旭光」之后，便是万千「繁星」 格蕾修正在画室里画画，她一共有 $n$ 种颜色（从 $1$ 到 $n$ 编号）的颜料。 一开始，画布上什么颜色也没有，接下来格蕾修进行了 $q$ 次操作，操作共有两种： 1.在画布上添加一种原本没有的颜色； 2.在画布上擦去一种原本存在的颜色。 定义两种不同的颜色 $x$ 关于 $y$ 的和谐度为 $x$ 除以 $y$ 的商加上余数，即 $\lfloor \frac{x}{y} \rfloor + x - \lfloor \frac{x}{y} \rfloor \times y$；定义整张画布的和谐度为从中任选两种存在的不同颜色得到的和谐度的最小值。 请你计算格蕾修每次操作完成后画布的和谐度，如果画布中存在的颜色不足 $2$ 种，则输出 $-1$。

Input

第一行输入一个正整数 $t\ (1\le t\le 5)$ 代表数据组数。 对于每组测试数据： 第一行 $2$ 个正整数 $n,q\ (1\leq n,q\leq 5\times10^4)$，分别表示颜色的数量和格蕾修操作的次数。 接下来共 $q$ 行，其中第 $i$ 行 $2$ 个整数 $opt_i,x_i\ (opt_i\in$ {$0,1$}$, 1\leq x_i\leq n)$。

• 如果 $opt_i=0$ 则表示在画布上擦去颜色 $x_i$，保证操作前画布上存在颜色 $x_i$；
• 如果 $opt_i=1$则表示在画布上添加颜色$x_i$，保证操作前画布上不存在颜色 $x_i$。

Output

共 $q$ 行，其中第 $i$ 行输出 $1$ 个整数表示格蕾修第 $i$ 次操作后画布的和谐度。

Sample Input

1
10 4
1 4
1 7
1 9
0 7

Sample Output

-1
4
3
3

Source

2024“钉耙编程”中国大学生算法设计超级联赛（3）