CF1930F.Maximize the Difference

For an array $b$ of $m$ non-negative integers, define $f(b)$ as the maximum value of $\max\limits_{i = 1}^{m} (b_i | x) - \min\limits_{i = 1}^{m} (b_i | x)$ over all possible non-negative integers $x$, where $|$ is bitwise OR operation.

You are given integers $n$ and $q$. You start with an empty array $a$. Process the following $q$ queries:

• $v$: append $v$ to the back of $a$ and then output $f(a)$. It is guaranteed that $0 \leq v \lt n$.

The queries are given in a modified way.

对于一个包含 $m$ 个非负整数的数组 $b$，定义 $f(b)$ 为：对所有可能的非负整数 $x$，表达式 $\max\limits_{i = 1}^{m} (b_i | x) - \min\limits_{i = 1}^{m} (b_i | x)$ 的最大值，其中 $|$ 表示按位或运算。

给定整数 $n$ 和 $q$。你从一个空数组 $a$ 开始，依次处理以下 $q$ 个查询：

• $v$：将 $v$ 追加到数组 $a$ 的末尾，然后输出 $f(a)$。保证 $0 \leq v \lt n$。

这些查询以一种修改后的方式给出。

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \leq n \leq 2^{22}$, $1 \leq q \leq 10^6$) — the number of queries.

The second line of each test case contains $q$ space-separated integers $e_1,e_2,\ldots,e_q$ ($0 \leq e_i \lt n$) — the encrypted values of $v$.

Let $\mathrm{last}_i$ equal the output of the $(i-1)$-th query for $i\geq 2$ and $\mathrm{last}_i=0$ for $i=1$. Then the value of $v$ for the $i$-th query is ($e_i + \mathrm{last}_i$) modulo $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2^{22}$ and the sum of $q$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含一个整数 $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 \lt n$）—— 即 $v$ 的加密值。

令 $\mathrm{last}_i$ 表示第 $(i-1)$ 次查询的输出结果（当 $i \geq 2$ 时），并规定 $\mathrm{last}_i = 0$（当 $i = 1$ 时）。则第 $i$ 次查询中 $v$ 的值为 $(e_i + \mathrm{last}_i) \bmod n$。

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

For each test case, print $q$ integers. The $i$-th integer is the output of the $i$-th query.

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

In the first test case, the final $a=[1,2]$. For $i=1$, the answer is always $0$, irrespective of $x$. For $i=2$, we can select $x=5$.

In the second test case, the final $a=[3,1,0,5]$.

在第一个测试用例中，最终的数组 $a=[1,2]$。对于 $i=1$，答案恒为 $0$，与 $x$ 的取值无关。对于 $i=2$，我们可以选择 $x=5$。

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