CF1930F Maximize the Difference

对于一个由 $m$ 个非负整数组成的数组 $b$，定义 $f(b)$ 为所有可能的非负整数 $x$ 下，$\max\limits_{i = 1}^{m} (b_i | x) - \min\limits_{i = 1}^{m} (b_i | x)$ 的最大值，其中 $|$ 表示[按位或运算](https://en.wikipedia.org/wiki/Bitwise_operation#OR)。 给定整数 $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-1$ 次查询的输出（对于 $i \geq 2$），$\mathrm{last}_1=0$。则第 $i$ 次查询的 $v$ 的值为 $(e_i + \mathrm{last}_i) \bmod n$。 保证所有测试用例中 $n$ 的总和不超过 $2^{22}$，所有测试用例中 $q$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $q$ 个整数，第 $i$ 个整数为第 $i$ 次查询的输出。

在第一个测试用例中，最终 $a=[1,2]$。对于 $i=1$，无论 $x$ 取何值，答案始终为 $0$。对于 $i=2$，我们可以选择 $x=5$。 在第二个测试用例中，最终 $a=[3,1,0,5]$。 由 ChatGPT 4.1 翻译