← 返回题目列表

Codeforces · 1930/F

F. 最大化差异

中文机器翻译题面 查看原题

对于 $$$m$$$ 非负整数的数组 $$$b$$$,将 $$$f(b)$$$ 定义为 $$$\max\limits_{i = 1}^{m} (b_i | x) - \min\limits_{i = 1}^{m} (b_i | x)$$$ 在所有可能的非负整数上的最大值$$$x$$$,其中$$$|$$$ 是按位或运算。

给定整数 $$$n$$$ 和 $$$q$$$。您从一个空数组 $$$a$$$ 开始。处理以下 $$$q$$$ 查询:

- $$$v$$$:将$$$v$$$追加到$$$a$$$后面,然后输出$$$f(a)$$$。保证 $$$0 \leq v < n$$$。

查询以修改后的方式给出。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 2^{22}$$$, $$$1 \leq q \leq 10^6$$$) — 查询数。

每个测试用例的第二行包含 $$$q$$$ 以空格分隔的整数 $$$e_1,e_2,\ldots,e_q$$$ ($$$0 \leq e_i < n$$$) — $$$v$$$ 的加密值。

令 $$$\mathrm{last}_i$$$ 等于 $$$i\geq 2$$$ 的第 $$$(i-1)$$$ 查询的输出,以及 $$$i=1$$$ 的 $$$\mathrm{last}_i=0$$$ 的输出。那么第 $$$i$$$ 个查询的 $$$v$$$ 的值是 ($$$e_i + \mathrm{last}_i$$$) 模 $$$n$$$。

保证所有测试用例的$$$n$$$总和不超过$$$2^{22}$$$,所有测试用例的$$$q$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印 $$$q$$$ 整数。第 $$$i$$$ 整数是第 $$$i$$$ 查询的输出。

示例

输入 #1

2
5 2
1 2
7 4
3 1 5 2

输出 #1

0 2
0 2 3 5

注意

在第一个测试用例中,最终的$$$a=[1,2]$$$。对于 $$$i=1$$$,无论 $$$x$$$ 是多少,答案始终是 $$$0$$$。对于$$$i=2$$$,我们可以选择$$$x=5$$$。

在第二个测试用例中,最终$$$a=[3,1,0,5]$$$。