311075: CF1930F. Maximize the Difference
Description
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 < n$.
The queries are given in a modified way.
InputEach 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 < 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$.
OutputFor each test case, print $q$ integers. The $i$-th integer is the output of the $i$-th query.
ExampleInput2 5 2 1 2 7 4 3 1 5 2Output
0 2 0 2 3 5Note
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]$.
Output
题目名为“最大化差值”。给定一个由非负整数组成的数组b，定义函数f(b)为在所有可能的非负整数x上，表达式max(b_i | x) - min(b_i | x)的最大值，其中“|”表示按位或操作。
题目输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 2 * 10^5），表示测试用例的数量。
- 每个测试用例包含以下内容：
- 第一行包含两个整数n和q（1 ≤ n ≤ 2^22，1 ≤ q ≤ 10^6），分别表示数字的范围和查询的数量。
- 第二行包含q个空格分隔的整数e_1, e_2, …, e_q（0 ≤ e_i < n），表示加密后的v值。
- 保证所有测试用例中n的总和不超过2^22，q的总和不超过10^6。
输出：
- 对于每个测试用例，输出q个整数，第i个整数表示第i个查询的输出。
例：
输入：
2
5 2
1 2
7 4
3 1 5 2
输出：
0 2
0 2 3 5
注意：
- 在第一个测试用例中，最终数组a=[1,2]。对于i=1，无论x的值如何，答案总是0。对于i=2，我们可以选择x=5。
- 在第二个测试用例中，最终数组a=[3,1,0,5]。题目大意： 题目名为“最大化差值”。给定一个由非负整数组成的数组b，定义函数f(b)为在所有可能的非负整数x上，表达式max(b_i | x) - min(b_i | x)的最大值，其中“|”表示按位或操作。 题目输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 2 * 10^5），表示测试用例的数量。 - 每个测试用例包含以下内容： - 第一行包含两个整数n和q（1 ≤ n ≤ 2^22，1 ≤ q ≤ 10^6），分别表示数字的范围和查询的数量。 - 第二行包含q个空格分隔的整数e_1, e_2, …, e_q（0 ≤ e_i < n），表示加密后的v值。 - 保证所有测试用例中n的总和不超过2^22，q的总和不超过10^6。 输出： - 对于每个测试用例，输出q个整数，第i个整数表示第i个查询的输出。 例： 输入： 2 5 2 1 2 7 4 3 1 5 2 输出： 0 2 0 2 3 5 注意： - 在第一个测试用例中，最终数组a=[1,2]。对于i=1，无论x的值如何，答案总是0。对于i=2，我们可以选择x=5。 - 在第二个测试用例中，最终数组a=[3,1,0,5]。