CF2103F.Maximize Nor

对于一个包含 $k$ 位整数的数组 $b_1, b_2, \ldots, b_m$，其按位或非运算$^{\text{∗}}$可以通过从左到右累积计算得到。更正式地说，对于 $m \ge 2$，$\operatorname{nor}(b_1, b_2, \ldots, b_m) = \operatorname{nor}(\operatorname{nor}(b_1, b_2, \ldots, b_{m - 1}), b_m)$，而 $\operatorname{nor}(b_1) = b_1$。

给定一个包含 $k$ 位整数的数组 $a_1, a_2, \ldots, a_n$。对于每个下标 $i$（$1 \le i \le n$），找出所有包含下标 $i$ 的子数组$^{\text{†}}$中按位或非运算的最大值。换句话说，对于每个下标 $i$，找出所有满足 $1 \le l \le i \le r \le n$ 的子数组 $a_l, a_{l+1}, \ldots, a_r$ 中 $\operatorname{nor}(a_l, a_{l+1}, \ldots, a_r)$ 的最大值。

$^{\text{∗}}$ 两个布尔值的逻辑或非运算定义为：当两个值都为 $0$ 时结果为 $1$，否则为 $0$。两个 $k$ 位整数的按位或非运算是对每对对应位进行逻辑或非运算得到的结果。

例如，将 $2$ 和 $6$ 表示为 $4$ 位二进制数时，计算 $\operatorname{nor}(2, 6)$。$2$ 的二进制表示为 $0010_2$，$6$ 为 $0110_2$。因此，$\operatorname{nor}(2,6) = 1001_2 = 9$，因为从左到右逐位进行逻辑或非运算：

• $\operatorname{nor}(0,0) = 1$
• $\operatorname{nor}(0,1) = 0$
• $\operatorname{nor}(1,0) = 0$
• $\operatorname{nor}(1,1) = 0$

注意，如果 $2$ 和 $6$ 表示为 $3$ 位整数，则 $\operatorname{nor}(2,6) = 1$。

$^{\text{†}}$ 数组 $x$ 是数组 $y$ 的子数组，当且仅当 $x$ 可以通过从 $y$ 的开头和结尾删除若干（可能为零或全部）元素得到。

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$1 \le k \le 17$）——数组的元素个数和数组元素的位数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 2^k - 1$）——数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数是所有包含下标 $i$ 的子数组中按位或非运算的最大值。

在第一个测试用例中：

• 包含下标 $1$ 的子数组有 $[1]$ 和 $[1, 3]$。它们的按位或非运算结果分别为 $1$ 和 $0$。因此，下标 $1$ 的答案为 $1$。
• 包含下标 $2$ 的子数组有 $[3]$ 和 $[1, 3]$。它们的按位或非运算结果分别为 $3$ 和 $0$。因此，下标 $2$ 的答案为 $3$。

在第二个测试用例中：

• 对于 $i = 1$，按位或非运算最大的子数组是 $[a_1, a_2, a_3, a_4, a_5] = [1, 7, 4, 6, 2]$，$\operatorname{nor}(1, 7, 4, 6, 2) = 5$。
• 对于 $i = 2$，按位或非运算最大的子数组是 $[a_2] = [7]$，$\operatorname{nor}(7) = 7$。
• 对于 $i = 3$，按位或非运算最大的子数组是 $[a_1, a_2, a_3, a_4, a_5] = [1, 7, 4, 6, 2]$，$\operatorname{nor}(1, 7, 4, 6, 2) = 5$。
• 对于 $i = 4$，按位或非运算最大的子数组是 $[a_4] = [6]$，$\operatorname{nor}(6) = 6$。
• 对于 $i = 5$，按位或非运算最大的子数组是 $[a_1, a_2, a_3, a_4, a_5] = [1, 7, 4, 6, 2]$，$\operatorname{nor}(1, 7, 4, 6, 2) = 5$。

翻译由 DeepSeek V3 完成